Complexity of the traveling tournament problem

DOI10.1016/J.TCS.2010.10.001MaRDI QIDQ620946zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) General theory of conformal mappings (30C35)

Recommendations

• Complexity of the unconstrained traveling tournament problem
• On the complexity of the traveling umpire problem
• An improved approximation algorithm for the traveling tournament problem
• Approximating the traveling tournament problem with maximum tour length 2
• An Improved Approximation Algorithm for the Traveling Tournament Problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2084735 (Why is no real title available?)
• A 2.75-approximation algorithm for the unconstrained traveling tournament problem
• A 5.875-approximation for the traveling tournament problem
• A simulated annealing approach to the traveling tournament problem
• An Improved Approximation Algorithm for the Traveling Tournament Problem
• An approximation algorithm for the traveling tournament problem
• Round robin scheduling -- a survey
• Scheduling in Sports
• Scheduling in sports: an annotated bibliography
• The complexity of finding maximum disjoint paths with length constraints

Cited in

(22)

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

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

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