Minimizing Breaks by Maximizing Cuts

Elf, Matthias and Jünger, Michael and Rinaldi, Giovanni (2003) Minimizing Breaks by Maximizing Cuts.
Published in: Operations Research Letters Vol. 31 (5). pp. 343-349.

Abstract

Jean Charles Régin and Michael Trick have proposed to solve the schedule generation problem for sports leagues in two phases in which the first generates a tournament schedule and the second fixes the home-away pattern so as to minimize the number of breaks. While constraint programming techniques appear to be the methods of choice for the first phase, we propose to solve the break minimization problem in sports scheduling by transforming it into a maximum cut problem in an undirected graph and applying a branch-and-cut algorithm. Our approach outperforms previous approaches with constraint programming and integer programming techniques.


Actions:
Download: [img] Postscript - Preprinted Version
Download (1MB) | Preview
Download: [img] PDF - Preprinted Version
Download (203kB) | Preview
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: [error in script] 45 (Google Scholar) | [error in script]
Uncontrolled Keywords: [error in script]
Subjects:
Uncontrolled Keywords: maximum cut, sports scheduling
Subjects: UNSPECIFIED
Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
Depositing User: Matthias Elf
Date Deposited: 19 Jul 2003 00:00
Last Modified: 19 Dec 2011 09:44
Deposit Information:
ZAIK Number: [error in script]
Depositing User: Matthias Elf
Date Deposited: 19 Jul 2003 00:00
Last Modified: 19 Dec 2011 09:44
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/409