A 2.75-approximation algorithm for the unconstrained traveling tournament problem

DOI10.1007/s10479-012-1161-yzbMath1301.90037arXiv1110.0620OpenAlexW3100949812MaRDI QIDQ475199

Ryuhei Miyashiro, Shinji Imahori, Tomomi Matsui

Publication date: 26 November 2014

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1110.0620

zbMATH Keywords

approximation algorithmtimetablesports schedulingtraveling tournament problem

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

Unconstrained traveling tournament problem is APX-complete ⋮ Complexity of the traveling tournament problem ⋮ A further improvement on approximating TTP-2 ⋮ Complexity of the unconstrained traveling tournament problem

Uses Software

• Gurobi
• Concorde

Cites Work

• Unnamed Item
• Complexity of the traveling tournament problem
• An improved approximation algorithm for the traveling tournament problem
• Scheduling in sports: an annotated bibliography
• An approximation algorithm for the traveling tournament problem
• Round robin scheduling -- a survey
• Maximizing breaks and bounding solutions to the mirrored traveling tournament problem
• Approximating the Traveling Tournament Problem with Maximum Tour Length 2