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

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].