An Improved Algorithm for a Bipartite Traveling Tournament in Interleague Sports Scheduling
针对二分旅行锦标赛问题，提出一种对任意n和常数k的近似算法，改进了此前仅对n=2k情形的近似比，可用于NBA等跨联盟赛程优化。
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 [Formula: see text]-approximation is known for the case that [Formula: see text]. Whether there are similar results for the cases that [Formula: see text] and [Formula: see text] was asked in the literature. In this paper, we answer this question positively by proposing a [Formula: see text]-approximation algorithm for any n and any constant [Formula: see text], which also improves the previous approximation ratio for the case that [Formula: see text]. Funding: This research was supported by the National Natural Science Foundation of China [Grants 62372095, 62172077, and 62350710215].