The traveling tournament problem: improved algorithms based on cycle packing

DOI10.1016/J.TCS.2025.115519MaRDI QIDQ6903536zbMATH OpenFDO

Authors Jingyang Zhao, Mingyu Xiao, Chao Xu

Publication date 10 November 2025

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

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115519

zbMATH Keywords

approximation algorithmssports schedulingtimetabling combinatorial optimizationtraveling tournament problem

Mathematics Subject Classification ID

Approximation algorithms (68W25) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

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 General Approximation Technique for Constrained Forest Problems
• 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)}\)
• Approximation results for the weighted \(P_4\) partition problem
• Complexity of the traveling tournament problem
• Complexity of the unconstrained traveling tournament problem
• scientific article; zbMATH DE number 3746840 (Why is no real title available?)
• scientific article; zbMATH DE number 3598198 (Why is no real title available?)
• scientific article; zbMATH DE number 2084735 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• Improved approximation algorithms for the traveling tournament problem
• Practical algorithms with guaranteed approximation ratio for traveling tournament problem with maximum tour length 2
• RobinX: a three-field classification and unified data format for round-robin sports timetabling
• Scheduling in Sports
• Unconstrained traveling tournament problem is APX-complete

This page was built for publication: The traveling tournament problem: improved algorithms based on cycle packing

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