A Better Approximation for Bipartite Traveling Tournament in Inter-League Sports Scheduling
A Better Approximation for Bipartite Traveling Tournament in Inter-League Sports Scheduling
Jingyang Zhao, Mingyu Xiao
Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence
Main Track. Pages 6814-6822.
https://doi.org/10.24963/ijcai.2024/753
The bipartite traveling tournament problem (BTTP) was initially introduced by Hoshino and Kawarabayashi (AAAI 2011) to address inter-league sports scheduling, which aims to design a feasible bipartite tournament between two n-team leagues under some constraints such that the total traveling distance of all participating teams is minimized. Since its introduction, several heuristic methods have been developed to design feasible schedules for NBA, NPB and so on. In terms of solution quality with a theoretical guarantee, previously only a (2+ε) approximation is known for the case that n≡0 (mod 3). Whether there are similar results for the cases that n≡1 (mod 3) and n≡2 (mod 3) was asked in the literature. In this paper, we answer this question positively by proposing a (3/2+ε)-approximation algorithm for any n and any constant ε>0, which also improves the previous ratio for the case that n≡0 (mod 3).
Keywords:
Planning and Scheduling: PS: Scheduling
Planning and Scheduling: PS: Routing
Planning and Scheduling: PS: Theoretical foundations of planning