Complexity of the traveling tournament problem

DOI10.1016/j.tcs.2010.10.001zbMath1230.90102OpenAlexW1972849741WikidataQ57851410 ScholiaQ57851410MaRDI QIDQ620946

Clemens Thielen, Stephan Westphal

Publication date: 2 February 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.10.001

zbMATH Keywords

computational complexityschedulingtimetablingtraveling tournament problem

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) General theory of conformal mappings (30C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Sports scheduling and other topics in sports analytics: a survey with special reference to Latin America ⋮ A combined local search and integer programming approach to the traveling tournament problem ⋮ A variable neighborhood search method for solving the traveling tournaments problem ⋮ Edge coloring: a natural model for sports scheduling ⋮ Unconstrained traveling tournament problem is APX-complete ⋮ Approximation algorithms for \(\mathrm{TTP(2)}\) ⋮ Round-robin scheduling with regard to rest differences ⋮ A polyhedral study for the cubic formulation of the unconstrained traveling tournament problem ⋮ A multi-round generalization of the traveling tournament problem and its application to Japanese baseball ⋮ A further improvement on approximating TTP-2 ⋮ Scheduling Argentina's professional basketball leagues: a variation on the travelling tournament problem ⋮ A 2.75-approximation algorithm for the unconstrained traveling tournament problem ⋮ A 5.875-approximation for the traveling tournament problem ⋮ Complexity of the unconstrained traveling tournament problem ⋮ Sports scheduling: Problems and applications ⋮ A beam search approach to the traveling tournament problem

Cites Work

• Unnamed Item
• Unnamed Item
• A 2.75-approximation algorithm for the unconstrained traveling tournament problem
• A 5.875-approximation for the traveling tournament problem
• Scheduling in sports: an annotated bibliography
• A simulated annealing approach to the traveling tournament problem
• An approximation algorithm for the traveling tournament problem
• Round robin scheduling -- a survey
• An Improved Approximation Algorithm for the Traveling Tournament Problem
• Scheduling in Sports
• The complexity of finding maximum disjoint paths with length constraints

This page was built for publication: Complexity of the traveling tournament problem