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

Jingyang Zhao () and Mingyu Xiao ()
Additional contact information
Jingyang Zhao: School of Computer Science and Engineering, School of Computer Science, University of Electronic Science and Technology of China, Chengdu 611731, China
Mingyu Xiao: School of Computer Science and Engineering, School of Computer Science, University of Electronic Science and Technology of China, Chengdu 611731, China

Mathematics of Operations Research, 2025, vol. 50, issue 2, 910-934

Abstract: 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%.

Keywords: Primary: 90B35; secondary: 68W25; sports scheduling; traveling tournament problem; approximation algorithms; timetabling combinatorial optimization (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.0356 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:50:y:2025:i:2:p:910-934

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().