A Better Approximation for Bipartite Traveling Tournament in Inter-League Sports Scheduling

Jingyang Zhao, Mingyu XiaoIJCAI 2024

Abstract

The Bipartite Traveling Tournament Problem (BTTP) is a fundamental challenge in sports scheduling, aiming to minimize total travel distance for inter-league play while adhering to strict constraints on consecutive home or away games. This paper presents a novel $(3/2 + \epsilon)$-approximation algorithm, significantly improving upon the long-standing $(2 + \epsilon)$ benchmark. The methodology leverages a new lower bound derived from minimum weight cycle packing and a construction strategy based on 3-path packing. Beyond theoretical improvements, the algorithm is shown to be highly efficient, producing near-optimal schedules for a 32-team NBA expansion instance in under one second.

Introduction

In sports analytics, the Traveling Tournament Problem (TTP) serves as a benchmark for complex scheduling. This paper focuses on the Bipartite version (BTTP), which models inter-league play, such as the NBA’s Eastern versus Western Conference. In BTTP, teams only play opponents from the opposing league. The schedule must satisfy the "Bounded-by-3" constraint: no team can play more than three consecutive home or away games, and teams must return home after the final game.

Previously, approximation ratios were only known for league sizes divisible by three, with the best ratio being 2.0. This paper addresses these gaps by providing a theoretical guarantee for almost all league sizes and tightening the approximation ratio to 1.5.

Methodology

A Novel Lower Bound

The authors' approach begins with establishing a tighter mathematical "floor" for the minimum possible travel distance. They achieve this by relating BTTP to minimum weight cycle packing—the task of finding a set of vertex-disjoint cycles that cover a graph with minimum total edge weight.

Conceptual diagram of cycle packing used to establish the new lower bound.

This relationship allows for a more precise estimation of the optimal travel distance, which is crucial for proving the improved approximation ratio.

3-Path Packing Construction

To build the schedule, the algorithm groups teams into "super-teams" and games into "super-games." The construction is centered on "3-path packing," which groups three vertices into a path to structure these super-games. This alignment ensures that teams move efficiently between venues while respecting the "Bounded-by-3" constraint.

A structured schedule table for a league with $n=6$ teams per conference.

As shown in the scheduling matrix above, the resulting construction is highly structured, allowing for predictable movement patterns that minimize the frequency of unnecessary home returns. To handle arbitrary league sizes $n$, the authors employ a randomized labeling method to assign teams to these 3-path structures, which can be derandomized into a deterministic algorithm.

Experimental Evaluation: The NBA-32 Instance

The paper evaluates the algorithm using both rigorous theoretical proofs and a practical real-world scenario. The authors created the NBA-32 dataset, simulating a 32-team expansion of the NBA. This instance includes two new teams in Las Vegas and Seattle, with distances calculated using the Haversine formula. This dataset is particularly significant as it represents a case where $n=16$ ($n \equiv 1 \pmod 3$), a size that previous algorithms could not theoretically guarantee.

Key Results

The proposed algorithm achieves several milestones:

  • Theoretical Improvement: The approximation ratio is reduced from $(2 + \epsilon)$ to $(3/2 + \epsilon)$ for nearly all $n$.
  • Computational Efficiency: The algorithm operates in $O(n^3)$ time, generating the NBA-32 schedule in less than one second.
  • Practical Performance: On the NBA-32 instance, the 3-path construction resulted in travel distances only 24.66% above the lower bound. A variant using 3-cycles performed even better, coming within 9.42% of the theoretical optimum.

Conclusion and Future Work

By exploiting the predictable structure of bipartite play and introducing cycle-packing lower bounds, the authors have significantly advanced the state of the art in sports scheduling. The "Power of 3" construction naturally aligns with the constraints of modern professional leagues. Future research may adapt these path-packing insights to the general Traveling Tournament Problem, which currently has a wider approximation gap.

Summary updated

BibTeX
@inproceedings{zhao2024better,
  author = {Jingyang Zhao and Mingyu Xiao},
  title = {{A Better Approximation for Bipartite Traveling Tournament in Inter-League Sports Scheduling}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure