An Improved Algorithm for a Bipartite Traveling Tournament in Interleague Sports Scheduling

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

摘要

The bipartite traveling tournament problem (BTTP) addresses interleague 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 methods have been developed to design feasible schedules for the National Basketball Association (NBA), Nippon Professional Baseball (NPB), and so on. In terms of solution quality with a theoretical guarantee, previously, only a (2 + epsilon)-approximation is known for the case that n equivalent to 0 (mod 3). Whether there are similar results for the cases that n equivalent to 1 (mod 3) and n equivalent to 2 (mod 3) was asked in the literature. In this paper, we answer this question positively by proposing a (3/2 + epsilon)-approximation algorithm for any n and any constant epsilon > 0, which also improves the previous approximation ratio for the case that n equivalent to 0 (mod 3).