The Inter-League Extension of the Traveling Tournament Problem and its Application to Sports Scheduling

With the recent inclusion of inter-league games to professional sports leagues, a natural question is to determine the "best possible" inter-league schedule that retains all of the league's scheduling constraints to ensure competitive balance and fairness, while minimizing the total travel distance for both economic and environmental efficiency. To answer that question, this paper introduces the Bipartite Traveling Tournament Problem (BTTP), the inter-league extension of the well-studied Traveling Tournament Problem. We prove that the 2n-team BTTP is NP-complete, but for small values of n, a distance-optimal inter-league schedule can be generated from an algorithm based on minimum-weight 4-cycle-covers. We apply our algorithm to the 12-team Nippon Professional Baseball (NPB) league in Japan, creating an inter-league tournament that reduces total team travel by 16% compared to the actual schedule played by these teams during the 2010 NPB season. We also analyze the problem of inter-league scheduling for the 30-team National Basketball Association (NBA), and develop a tournament schedule whose total inter-league travel distance is just 3.8% higher than the trivial theoretical lower bound.