Sports tournaments, home–away assignments, and the break minimization problem

Sports tournaments, home–away assignments, and the break minimization problem

0.00 Avg rating0 Votes
Article ID: iaor2007815
Country: Netherlands
Volume: 3
Issue: 2
Start Page Number: 165
End Page Number: 173
Publication Date: Jun 2006
Journal: Discrete Optimization
Authors: ,
Keywords: timetabling
Abstract:

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 1/4n(n−2) breaks. Secondly, for infinitely many n, we construct opponent schedules for which at least 1/6n(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=3. This is in strong contrast to the case of r=2 rounds, which can be scheduled (in polynomial time) without any breaks.

Reviews

Required fields are marked *. Your email address will not be published.