A 2.75-approximation algorithm for the unconstrained traveling tournament problem

DOI10.1007/S10479-012-1161-YzbMATH Open1301.90037arXiv1110.0620OpenAlexW3100949812MaRDI QIDQ475199FDOQ475199

Authors: Shinji Imahori, Tomomi Matsui, Ryuhei Miyashiro 

Publication date: 26 November 2014

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

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.

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

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

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)

Cites Work

• An approximation algorithm for the traveling tournament problem
• Title not available (Why is that?)
• Complexity of the traveling tournament problem
• Scheduling in sports: an annotated bibliography
• 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
• An improved approximation algorithm for the traveling tournament problem

Cited In (9)

• Complexity of the unconstrained traveling tournament problem
• Complexity of the traveling tournament problem
• A Benders approach for computing lower bounds for the mirrored 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
• An improved approximation algorithm for the traveling tournament problem
• A polyhedral study for the cubic formulation of the unconstrained traveling tournament problem
• An Improved Approximation Algorithm for the Traveling Tournament Problem

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)