Sports tournaments, home–away assignments, and the break minimization problem |
| |
Authors: | Gerhard Post Gerhard J Woeginger |
| |
Institution: | aDepartment of Applied Mathematics, University Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands;bDepartment of Mathematics and Computer Science, TU Eindhoven, P.O. Box 513, 5600 MB Eindhoven, The Netherlands |
| |
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 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. |
| |
Keywords: | Sports scheduling Time tabling Computational complexity |
本文献已被 ScienceDirect 等数据库收录! |
|