Dependent Randomized Rounding to the Home-Away Assignment Problem in Sports Scheduling

Ayami SUZUKA; Ryuhei MIYASHIRO; Akiko YOSHISE; Tomomi MATSUI

doi:10.1093/ietfec/e89-a.5.1407

Dependent Randomized Rounding to the Home-Away Assignment Problem in Sports Scheduling

Ayami SUZUKA, Ryuhei MIYASHIRO, Akiko YOSHISE, Tomomi MATSUI

Full Text Views

0

Share
Cite this

Summary :

Suppose that we have a timetable of a round-robin tournament with a number of teams, and distances among their homes. The home-away assignment problem is to find a home-away assignment that minimizes the total traveling distance of the teams. We propose a formulation of the home-away assignment problem as an integer program, and a rounding algorithm based on Bertsimas, Teo and Vohra's dependent randomized rounding method [2]. Computational experiments show that our method quickly generates feasible solutions close to optimal.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E89-A No.5 pp.1407-1416

Publication Date: 2006/05/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e89-a.5.1407

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Ayami SUZUKA, Ryuhei MIYASHIRO, Akiko YOSHISE, Tomomi MATSUI, "Dependent Randomized Rounding to the Home-Away Assignment Problem in Sports Scheduling" in IEICE TRANSACTIONS on Fundamentals, vol. E89-A, no. 5, pp. 1407-1416, May 2006, doi: 10.1093/ietfec/e89-a.5.1407.
Abstract: Suppose that we have a timetable of a round-robin tournament with a number of teams, and distances among their homes. The home-away assignment problem is to find a home-away assignment that minimizes the total traveling distance of the teams. We propose a formulation of the home-away assignment problem as an integer program, and a rounding algorithm based on Bertsimas, Teo and Vohra's dependent randomized rounding method [2]. Computational experiments show that our method quickly generates feasible solutions close to optimal.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e89-a.5.1407/_p

Copy

@ARTICLE{e89-a_5_1407,
author={Ayami SUZUKA, Ryuhei MIYASHIRO, Akiko YOSHISE, Tomomi MATSUI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Dependent Randomized Rounding to the Home-Away Assignment Problem in Sports Scheduling},
year={2006},
volume={E89-A},
number={5},
pages={1407-1416},
abstract={Suppose that we have a timetable of a round-robin tournament with a number of teams, and distances among their homes. The home-away assignment problem is to find a home-away assignment that minimizes the total traveling distance of the teams. We propose a formulation of the home-away assignment problem as an integer program, and a rounding algorithm based on Bertsimas, Teo and Vohra's dependent randomized rounding method [2]. Computational experiments show that our method quickly generates feasible solutions close to optimal.},
keywords={},
doi={10.1093/ietfec/e89-a.5.1407},
ISSN={1745-1337},
month={May},}

Copy

TY - JOUR
TI - Dependent Randomized Rounding to the Home-Away Assignment Problem in Sports Scheduling
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1407
EP - 1416
AU - Ayami SUZUKA
AU - Ryuhei MIYASHIRO
AU - Akiko YOSHISE
AU - Tomomi MATSUI
PY - 2006
DO - 10.1093/ietfec/e89-a.5.1407
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E89-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2006
AB - Suppose that we have a timetable of a round-robin tournament with a number of teams, and distances among their homes. The home-away assignment problem is to find a home-away assignment that minimizes the total traveling distance of the teams. We propose a formulation of the home-away assignment problem as an integer program, and a rounding algorithm based on Bertsimas, Teo and Vohra's dependent randomized rounding method [2]. Computational experiments show that our method quickly generates feasible solutions close to optimal.
ER -