Round robin tournaments and three index assignments

D. Briskorn, A. Drexl, F.C.R. Spieksma

Research output: Contribution to journalArticleAcademicpeer-review

11 Citations (Scopus)

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 languageEnglish
Pages (from-to)365-374
Journal4OR : A Quarterly Journal of Operations Research
Volume8
Issue number4
DOIs
Publication statusPublished - Dec 2010
Externally publishedYes

Keywords

  • Combinatorial optimization
  • Computational complexity
  • Sports league scheduling
  • Round robin tournaments
  • Planar three index assignments

Cite this