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

Jingyang Zhao, Mingyu Xiao · 2025

Read An Improved Algorithm for a Bipartite Traveling Tournament in Interleague Sports Scheduling by Jingyang Zhao, Mingyu Xiao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-06828.txt.

Introduction

Jingyang Zhao and Mingyu Xiao improve an approximation algorithm for sports scheduling in this two thousand twenty-five paper. The bipartite traveling tournament problem designs a tournament between two leagues of n teams each, under feasibility constraints, minimizing total travel distance. It models real interleague schedules such as those in professional basketball and baseball leagues. Previously, a guarantee slightly above a factor of two was known only when n was divisible by three.

Open cases remained when n left remainders one or two on division by three. The authors answer the question positively with an algorithm guaranteeing within a factor of about one and a half of optimal, for any n. That bound also improves the earlier result for the divisible-by-three case. The work closes a gap in the problem's approximation theory.

Catalog record

CREATORJingyang Zhao, Mingyu Xiao
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE85 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-06828

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Improved Algorithm for a Bipartite Traveling Tournament in Interleague Sports Scheduling Jingyang Zhao, Mingyu Xiao Abstract The bipartite traveling tournament problem (BTTP) addresses inter-league sports scheduling, which aims to design a feasible bipartite tournament between two n 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 NBA, NPB and so on. In terms of solution quality with a theoretical guarantee, previously only a ( 2 + ε ) (2+\varepsilon) -approximation is known for the case that n ≡ 0 ( mod 3 ) n\equiv 0\pmod{3} . Whether there are similar results for the cases that n ≡ 1 ( mod 3 ) n\equiv 1\pmod{3} and n ≡ 2 ( mod 3 ) n\equiv 2\pmod{3} was asked in the literature. In this paper, we answer this question positively by proposing a ( 3 / 2 + ε ) (3/2+\varepsilon) -approximation algorithm for any n n and any constant ε > 0 \varepsilon>0 , which also improves the previous approximation ratio for the case that n ≡ 0 ( mod 3 ) n\equiv 0\pmod{3} . 1 Introduction The traveling tournament problem (TTP), introduced by Easton et al. [ 7 ] , is a well-known benchmark problem in the field of sports scheduling [ 20 ] . This problem aims to find a double round-robin tournament, minimizing the total traveling distance of all participating teams. In a double round-robin tournament involving n teams (where n is even), each team plays two games against each of the other n-1 teams that includes one home game at its own home venue and one away game at its opponent’s home venue, and on each day each team can only play one game. Moreover, all games should be scheduled on 2(n-1) consecutive days, subject to several constraints on the maximum number of consecutive home/away games for each team, ensuring a balanced tournament arrangement. In the problem, we consider that the distance is a semi-metric, i.e., it satisfies the symmetry and triangle inequality properties. An overview of TTP and its variants, along with their various applications on sports scheduling, can be found in [ 2 , 6 ] . The bipartite traveling tournament problem (BTTP), introduced by Hoshino and Kawarabayashi [ 15 ] , is an inter-league extension of TTP. Given two n -team leagues, it asks for a distance-optimal double round-robin bipartite tournament between the leagues, where every team in one league plays one home game and one away game against each team in another league. It also requires that each team plays only one game on each day, and all games need to be scheduled on 2n consecutive days. For TTP/BTTP, the double round-robin (bipartite) tournament is subject to the following three basic constraints or assumptions: • No-repeat : No pair of teams can play against each other in two consecutive games. • direct-traveling : Each team travels directly from its game venue on the i -th day to its game venue on the (i+1) -th day, where we assume that all teams are initially at home before the first game starts and will return home after the last game ends. • Bounded-by-3 : Each team can play at most 3-consecutive home games or away games. In the last constraint, we require that the maximum number of consecutive home/away games for each team is at most three. This is the most extensively studied case [ 22 , 1 , 10 ] . The case that at most two consecutive home/away games are allowed is also studied in some references [ 26 , 3 , 33 ] . A small number of consecutive home/away games requires teams to return home frequently, which may make the tournament balanced at a cost of a possible longer traveling distance. As indicated in a previous study [ 16 ] , BTTP has potential applications in sports scheduling, such as for events like the Davis Cup, the biennial Ryder Cup, the National Basketball Association (NBA), and the Nippon Professional Baseball (NPB). Specifically, the NPB inter-league scheduling problem is precisely BTTP for the case n=6 [ 16 ] . Exploring BTTP also holds promise for advancing the theoretical development of enhanced algorithms for TTP. For instance, Zhao and Xiao [ 34 ] utilized an approximation algorithm for BTTP between two groups by grouping teams and achieved an efficient polynomial-time approximation scheme for a special case of TTP where all teams are positioned along a line. BTTP possesses a simpler structure, and scheduling for TTP can be derived from scheduling for BTTP using a divide-and-conquer method [ 3 , 37 ] . Therefore, effective algorithms for BTTP have the potential to yield effective algorithms for TTP as well. 1.1 Related Work Both TTP and BTTP are difficult optimization problems, and their NP-hardness has been established in [ 25 , 15 ] . In the online benchmark [ 27 , 2 ] , many instances of TTP with more than ten teams have not been completely solved even by using high-performance machines. TTP and BTTP have been extensively studied both in theory [ 17 , 18 , 28 , 30 , 19 , 32 , 36 ] and practice [ 8 , 5 , 13 , 14 , 15 , 16 , 11 , 9 ] . TTP and BTTP are also rich problems in approximation algorithms. An algorithm is called an \alpha -approximation algorithm if it can generate a feasible schedule in polynomial time such that the total traveling distance of all teams is within \alpha times the optimal. For TTP, Miyashiro et al. [ 23 ] first proposed a (2+\varepsilon) -approximation algorithm where \varepsilon is an arbitrary fixed constant, and the ratio was later improved to (1.667+\varepsilon) by Yamaguchi et al. [ 31 ] , and (1.598+\varepsilon) by Zhao et al. [ 38 ] . For BTTP, the only known result is a (2+\varepsilon) -approximation algorithm for the case that n\equiv 0\pmod{3} , proposed by Hoshino and Kawarabayashi [ 18 ] , and whether there exist similar algorithms for the cases that n\equiv 1\pmod{3} and n\equiv 2\pmod{3} was asked in this paper. 1.2 Our Results In this paper, we design a new algorithm for BTTP and prove that our algorithm can achieve an approximation ratio of (3/2+\varepsilon) for any n and any constant \varepsilon>0 . This not only positively answers the open question for the cases that n\equiv 1\pmod{3} and n\equiv 2\pmod{3} but also improves the previous best ratio of (2+\varepsilon) for the case that n\equiv 0\pmod{3} [ 18 ] . To achieve our improvement, in Section 3 , we propose a novel 3-path construction : given any (feasible) 3-path packing, it can compute a feasible schedule for BTTP in polynomial time. In Section 4 , we do some analysis. Specifically, in Section 4.1 , we introduce a novel lower bound for any optimal solution to BTTP, which is related to the minimum weight cycle packing (i.e., a set of cycles where each cycle has an order of at least 3). In Section 4.2 , we analyze the quality of the 3-path construction and show that the quality of the

Read the complete text