2021/08/30 by Jingyang Zhao, Zhao, Jingyang, Mingyu Xiao +1 · 1 citation
Computer Science · Decision Sciences · Engineering · Mathematics · Psychology · #Approximation algorithm #Benchmark (surveying) #Combinatorics #Computer science #Constraint (computer-aided design) #Data Structures and Algorithms (cs.DS) #Educational Games and Gamification #FOS: Computer and information sciences #Mathematical optimization #Mathematics #Schedule #Scheduling (production processes) #Scheduling and Timetabling Solutions #Tournament #Vehicle Routing Optimization Methods #cs.DS
paper · pdf · doi:10.48550/arxiv.2108.13060
16 pages, presented at COCOON 2021
arxiv created 2021/08/30 · openalex publication_date 2021/08/30 · arxiv updated 2021/08/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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 with one more constraint that each team can have at most two consecutive home games or away games. Due to the different structural properties, known algorithms for TTP-2 are different for n/2 being odd and even. For odd n/2, the best known approximation ratio is about (1+12/n), and for even n/2, the best known approximation ratio is about (1+4/n). In this paper, we further improve the approximation ratio from (1+4/n) to (1+3/n) for n/2 being even. Experimental results on benchmark sets show that our algorithm can improve previous results on all instances with even n/2 by 1% to 4%.