The Linear Distance Traveling Tournament Problem Allows an EPTAS
Abstract
The Traveling Tournament Problem (TTP-k) is a well-known benchmark problem in tournament timetabling and has been extensively studied in the field of AI. In this problem, we are going to design a double round-robin schedule such that each pair of teams plays one game in each other's home venue, minimizing the total distance traveled by all n teams (n is even) under the constraint that each team can have at most k-consecutive home games or away games. The Linear Distance Traveling Tournament Problem (LDTTP-k), where all teams are located on a line, was introduced by Hoshino and Kawarabayashi (AAAI 2012). For LDTTP-3, they gave a 4/3-approximation algorithm for n≡4 (mod 6) teams. In this paper, we show that for any 3≤k=o(∛n), LDTTP-k allows an efficient polynomial-time approximation scheme (EPTAS).
BibTeX
@article{Zhao_Xiao_2023, title={The Linear Distance Traveling Tournament Problem Allows an EPTAS}, volume={37}, url={https://ojs.aaai.org/index.php/AAAI/article/view/26433}, DOI={10.1609/aaai.v37i10.26433}, abstractNote={The Traveling Tournament Problem (TTP-k) is a well-known benchmark problem in tournament timetabling and has been extensively studied in the field of AI. In this problem, we are going to design a double round-robin schedule such that each pair of teams plays one game in each other’s home venue, minimizing the total distance traveled by all n teams (n is even) under the constraint that each team can have at most k-consecutive home games or away games. The Linear Distance Traveling Tournament Problem (LDTTP-k), where all teams are located on a line, was introduced by Hoshino and Kawarabayashi (AAAI 2012). For LDTTP-3, they gave a 4/3-approximation algorithm for n≡4 (mod 6) teams. In this paper, we show that for any 3≤k=o(∛n), LDTTP-k allows an efficient polynomial-time approximation scheme (EPTAS).}, number={10}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Zhao, Jingyang and Xiao, Mingyu}, year={2023}, month={Jun.}, pages={12155-12162} }