A 2.75-approximation algorithm for the unconstrained traveling tournament problem

DOI10.1007/S10479-012-1161-YMaRDI QIDQ475199zbMATHOpenAlexFDO

Authors Shinji Imahori, Tomomi Matsui, Ryuhei Miyashiro

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

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

Abstract: A 2.75-approximation algorithm is proposed for the unconstrained traveling tournament problem, which is a variant of the traveling tournament problem. For the unconstrained traveling tournament problem, this is the first proposal of an approximation algorithm with a constant approximation ratio. In addition, the proposed algorithm yields a solution that meets both the no-repeater and mirrored constraints. Computational experiments show that the algorithm generates solutions of good quality.

Recommendations

• An Improved Approximation Algorithm for the Traveling Tournament Problem
• An improved approximation algorithm for the traveling tournament problem
• An approximation algorithm for the traveling tournament problem
• An improved approximation algorithm for the traveling tournament problem with maximum trip length two
• A 5.875-approximation for the traveling tournament problem

Cites work

• scientific article; zbMATH DE number 2084735 (Why is no real title available?)
• An approximation algorithm for the traveling tournament problem
• An improved approximation algorithm for the traveling tournament problem
• Approximating the traveling tournament problem with maximum tour length 2
• Complexity of the traveling tournament problem
• Maximizing breaks and bounding solutions to the mirrored traveling tournament problem
• Round robin scheduling -- a survey
• Scheduling in sports: an annotated bibliography

Cited in

(9)

• Complexity of the unconstrained traveling tournament problem
• An improved approximation algorithm for the traveling tournament problem
• A polyhedral study for the cubic formulation of the unconstrained traveling tournament problem
• A Benders approach for computing lower bounds for the mirrored traveling tournament problem
• An Improved Approximation Algorithm for the Traveling Tournament Problem
• Complexity of the traveling tournament problem
• A further improvement on approximating TTP-2
• Unconstrained traveling tournament problem is APX-complete
• An approximation algorithm for the traveling tournament problem

Describes a project that uses

Uses Software

• Gurobi
• Concorde

This page was built for publication: A 2.75-approximation algorithm for the unconstrained traveling tournament problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q475199)