Practical Algorithms with Guaranteed Approximation Ratio for Traveling Tournament Problem with Maximum Tour Length 2

• 成果类型: Article
• 署名作者: Zhao, Jingyang; Xiao, Mingyu
• 署名单位: University of Electronic Science & Technology of China
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.0356
• 发表日期: 2025
• 关键词: Complexity

摘要

The traveling tournament problem (TTP) is a hard but interesting sports scheduling problem inspired by Major League Baseball, which is 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). In this paper, we consider TTP-2 (i.e., TTP under the constraint that at most two consecutive home games or away games are allowed for each team). In this paper, we propose practical algorithms for TTP-2 with improved approximation ratios. Because of the different structural properties of the problem, all known algorithms for TTP-2 are different for n/2 being odd and even, and our algorithms are also different for these two cases. For even n/2, our approximation ratio is 1 + 3/n, improving the previous result of 1 + 4/n. For odd n/2, our approximation ratio is 1 + 5/n, improving the previous result of 3/2 + 6/n. In practice, our algorithms are easy to implement. Experiments on well-known benchmark sets show that our algorithms beat previously known solutions for all instances with an average improvement of 5.66%.