TY - JOUR
T1 - Sports tournaments, home-away assignments, and the break minimization problem
AU - Post, G.F.
AU - Woeginger, G.J.
PY - 2006
Y1 - 2006
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 breaks. Secondly, for infinitely many n, we construct opponent schedules for which at least 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=3. 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 breaks. Secondly, for infinitely many n, we construct opponent schedules for which at least 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=3. This is in strong contrast to the case of r=2 rounds, which can be scheduled (in polynomial time) without any breaks.
U2 - 10.1016/j.disopt.2005.08.009
DO - 10.1016/j.disopt.2005.08.009
M3 - Article
VL - 3
SP - 165
EP - 173
JO - Discrete Optimization
JF - Discrete Optimization
SN - 1572-5286
IS - 2
ER -