A 5-approximation algorithm for the traveling tournament problem

DOI10.1007/S10479-025-06483-1MaRDI QIDQ7002466zbMATH OpenFDO

Authors Jingyang Zhao, Mingyu Xiao

Publication date 3 April 2025

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

Full work available at URL https://doi.org/10.1007/S10479-025-06483-1

zbMATH Keywords

approximation algorithmscombinatorial optimizationsports schedulingtimetablingtraveling tournament problem

Mathematics Subject Classification ID

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

Cites work

• A (slightly) improved approximation algorithm for metric TSP
• A 2.75-approximation algorithm for the unconstrained traveling tournament problem
• A 5.875-approximation for the traveling tournament problem
• A combined local search and integer programming approach to the traveling tournament problem
• A further improvement on approximating TTP-2
• A simulated annealing and hill-climbing algorithm for the traveling tournament problem
• A simulated annealing approach to the traveling tournament problem
• An approximation algorithm for the bipartite traveling tournament problem
• An approximation algorithm for the traveling tournament problem
• An improved approximation algorithm for the traveling tournament problem
• An improved approximation algorithm for the traveling tournament problem with maximum trip length two
• An improved scheduling algorithm for traveling tournament problem with maximum trip length two
• Approximation algorithms for \(\mathrm{TTP(2)}\)
• Complexity of the traveling tournament problem
• Complexity of the unconstrained traveling tournament problem
• Generating approximate solutions to the TTP using a linear distance relaxation
• scientific article; zbMATH DE number 3746840 (Why is no real title available?)
• scientific article; zbMATH DE number 2084735 (Why is no real title available?)
• Improved approximation algorithms for the traveling tournament problem
• RobinX: a three-field classification and unified data format for round-robin sports timetabling
• Scheduling in sports: an annotated bibliography
• Some models of graphs for scheduling sports competitions
• Sports scheduling and other topics in sports analytics: a survey with special reference to Latin America
• Unconstrained traveling tournament problem is APX-complete
• Worst-case analysis of a new heuristic for the travelling salesman problem

Cited in

(2)

• The APX-hardness of the traveling tournament problem
• A matching-based approximation algorithm for the traveling tournament problem

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

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