A Matching-Based Algorithm for the Traveling Tournament Problem
Abstract
The Traveling Tournament Problem (TTP-k) is a well-known benchmark problem in tournament timetabling. It involves designing a feasible double round-robin tournament for a sports league of n teams under several feasibility requirements, while minimizing the total traveling costs of the teams. The parameter k requires that in the tournament at most k consecutive home games or away games for each team are allowed. TTP-k with a small k, especially for k=2,3 and 4, have been extensively studied in the literature. In this paper, we focus on TTP-4 and design an efficient algorithm for it based on minimum weight matching. In theory, we prove that our algorithm has an approximation ratio of 1.625+ε for any constant ε>0, improving the best-known approximation ratio of 1.7+ε. In practice, our experimental results indicate an average improvement of 6.65% over the best-known solutions on 9 benchmark instances.
BibTeX
@article{Zhao_Xiao_2025, title={A Matching-Based Algorithm for the Traveling Tournament Problem}, volume={39}, url={https://ojs.aaai.org/index.php/AAAI/article/view/34878}, DOI={10.1609/aaai.v39i25.34878}, abstractNote={The Traveling Tournament Problem (TTP-k) is a well-known benchmark problem in tournament timetabling. It involves designing a feasible double round-robin tournament for a sports league of n teams under several feasibility requirements, while minimizing the total traveling costs of the teams. The parameter k requires that in the tournament at most k consecutive home games or away games for each team are allowed. TTP-k with a small k, especially for k=2,3 and 4, have been extensively studied in the literature. In this paper, we focus on TTP-4 and design an efficient algorithm for it based on minimum weight matching. In theory, we prove that our algorithm has an approximation ratio of 1.625+ε for any constant ε>0, improving the best-known approximation ratio of 1.7+ε. In practice, our experimental results indicate an average improvement of 6.65% over the best-known solutions on 9 benchmark instances.}, number={25}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Zhao, Jingyang and Xiao, Mingyu}, year={2025}, month={Apr.}, pages={26750-26758} }