Abstract
| Original language | Undefined |
|---|---|
| Place of Publication | Enschede |
| Publisher | University of Twente |
| Number of pages | 14 |
| ISBN (Print) | 0169-2690 |
| Publication status | Published - 2005 |
Publication series
| Name | Memorandum Afdeling TW |
|---|---|
| Publisher | Department of Applied Mathematics, University of Twente |
| No. | 1760 |
| ISSN (Print) | 0169-2690 |
Keywords
- MSC-90B35
- METIS-225439
- IR-65944
- EWI-3580
Cite this
}
Sports tournaments, home-away assignments, and the break minimization problem. / Post, Gerhard F.; Woeginger, Gerhard.
Enschede : University of Twente, 2005. 14 p. (Memorandum Afdeling TW; No. 1760).Research output: Book/Report › Report › Professional
TY - BOOK
T1 - Sports tournaments, home-away assignments, and the break minimization problem
AU - Post, Gerhard F.
AU - Woeginger, Gerhard
N1 - Imported from MEMORANDA
PY - 2005
Y1 - 2005
N2 - We consider the break minimization problem for fixing home-away assignments in round-robin sports tournaments. First, we show that for an opponent schedule with $n$ teams and $n-1$ rounds, there always exists a home-away assignment with at most $\frac14 n(n-2)$ breaks. Secondly, for infinitely many $n$, we construct opponent schedules for which at least $\frac16 n(n-1)$ breaks are necessary. Finally, we prove that break minimization for $n$ teams and a partial opponent schedule with $r$ rounds is an NP-hard problem for $r\ge3$. This is in strong contrast to the case of $r=2$ rounds, which can be scheduled (in polynomial time) without any breaks.
AB - We consider the break minimization problem for fixing home-away assignments in round-robin sports tournaments. First, we show that for an opponent schedule with $n$ teams and $n-1$ rounds, there always exists a home-away assignment with at most $\frac14 n(n-2)$ breaks. Secondly, for infinitely many $n$, we construct opponent schedules for which at least $\frac16 n(n-1)$ breaks are necessary. Finally, we prove that break minimization for $n$ teams and a partial opponent schedule with $r$ rounds is an NP-hard problem for $r\ge3$. This is in strong contrast to the case of $r=2$ rounds, which can be scheduled (in polynomial time) without any breaks.
KW - MSC-90B35
KW - METIS-225439
KW - IR-65944
KW - EWI-3580
M3 - Report
SN - 0169-2690
T3 - Memorandum Afdeling TW
BT - Sports tournaments, home-away assignments, and the break minimization problem
PB - University of Twente
CY - Enschede
ER -