Round robin tournaments and three index assignments |
| |
Authors: | Dirk Briskorn Andreas Drexl Frits C R Spieksma |
| |
Institution: | 1. Seminar für ABWL, Supply Chain Management und Produktion, Universit?t zu K?ln, Albertus-Magnus-Platz, 50923, K?ln, Germany 2. Lehrstuhl für Produktion und Logistik, Christian-Albrechts-Universit?t Kiel, 24098, Kiel, Germany 3. Department of Operations Research and Business Statistics, Katholieke Universiteit Leuven, Naamsestraat 69, 3000, Leuven, Belgium
|
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|