Abstract
Scheduling a sports league can be seen as a difficult combinatorial optimization problem. We study some variants of round robin tournaments and analyze the relationship with the planar three-index assignment problem. The complexity of scheduling a minimum cost round robin tournament is established by a reduction from the planar three-index assignment problem. Furthermore, we introduce integer programming models. We pick up a popular idea and decompose the overall problem in order to obtain two subproblems which can be solved sequentially. We show that the latter subproblem can be casted as a planar three-index assignment problem. This makes existing solution techniques for the planar three-index assignment problem amenable to sports league scheduling.
Original language | English |
---|---|
Pages (from-to) | 365-374 |
Journal | 4OR : A Quarterly Journal of Operations Research |
Volume | 8 |
Issue number | 4 |
DOIs | |
Publication status | Published - Dec 2010 |
Externally published | Yes |
Keywords
- Combinatorial optimization
- Computational complexity
- Sports league scheduling
- Round robin tournaments
- Planar three index assignments