The Traveling Tournament Problem with Maximum Tour Length Two: A Practical Algorithm with An Improved Approximation Bound

Jingyang Zhao, Mingyu XiaoIJCAI 2021 · DOI

TL;DR

This paper introduces a new algorithm for the Traveling Tournament Problem with a maximum of two consecutive home or away games (TTP-2). The algorithm achieves a near-optimal approximation ratio of $1 + O(1/n)$ for a specific case ($n/2$ being odd), significantly improving upon previous bounds and answering an open research question. Furthermore, it demonstrates strong practical performance, outperforming existing solutions on benchmark datasets.

What Problem Does This Paper Address?

The Traveling Tournament Problem (TTP) is a challenging scheduling problem that aims to minimize the total travel distance for all teams in a league, given a set of constraints. A common variant, TTP-k, adds a constraint that no team can have more than k consecutive home or away games. This paper focuses on TTP-2, where k=2. This constraint is considered important because it reflects real-world sports scheduling preferences for balancing home stands and road trips.

A key challenge in TTP-2 is finding feasible schedules, especially for cases where $n/2$ is odd. While previous work established a 2-approximation for TTP-2 and a $3/2 + O(1/n)$ approximation for the $n/2$ odd case, it remained an open question whether a $1 + O(1/n)$ approximation was achievable for this specific scenario. This paper tackles this open problem by developing a novel algorithm that not only provides a theoretically improved approximation bound but also performs well in practice.

Methods

The authors propose a constructive algorithm for TTP-2 when $n/2$ is odd. The core idea is to build a schedule by first arranging "super-games" between "super-teams." A super-team is formed by a pair of teams that are matched in a minimum perfect matching of the complete graph representing all teams. This approach simplifies the problem by reducing the number of entities to schedule from $n$ teams to $n/2$ super-teams.

The algorithm then systematically extends these super-games into normal games between individual teams. It defines specific scheduling patterns for different types of super-games: "middle," "left," and "right" super-games, each corresponding to different pairings of super-teams. These patterns are carefully designed to ensure feasibility and minimize travel distance. The construction also accounts for the specific cases of $n = 2 \pmod 8$ and $n = 6 \pmod 8$, where certain edge directions in the super-game graphs need to be reversed.

The theoretical analysis leverages the concept of a "perfect itinerary" (an itinerary that achieves a lower bound on travel distance for a single team) and uses Lemma 2, which states that the travel distance of any feasible itinerary is at most the optimal itinerary's distance plus the distance to the team's home venue. By bounding the "extra" travel distance incurred by their construction compared to perfect itineraries, they derive the improved approximation ratio.

Datasets

The paper evaluates its algorithm on benchmark datasets from Michael Trick's challenge instances for the Traveling Tournament Problem. Specifically, they tested on 62 instances with $n \ge 10$ and $n = 2 \pmod 4$. For their experimental comparison, they focused on 16 instances that had previously known best results.

Key Insights and Ideas

  • Bridging Theory and Practice: The paper successfully bridges a theoretical gap by providing the first $1 + O(1/n)$ approximation algorithm for TTP-2 when $n/2$ is odd, answering a long-standing open problem. Simultaneously, the algorithm is designed to be practical and efficient.
  • Super-Team Abstraction: The use of "super-teams" derived from a minimum perfect matching is a clever way to simplify the complex scheduling problem, allowing for a more structured construction.
  • Case-Specific Scheduling: Recognizing that the scheduling needs to differ slightly for $n = 2 \pmod 8$ and $n = 6 \pmod 8$ demonstrates a nuanced understanding of the problem's combinatorial structure.
  • Empirical Validation: The algorithm not only achieves theoretical improvements but also consistently outperforms previous best-known solutions on real-world benchmark instances, highlighting its practical utility.

Key Results

  • Theoretical Improvement: The paper proves a theoretical approximation ratio of $1 + O(1/n)$ for TTP-2 when $n/2$ is odd, a significant improvement over the previous $3/2 + O(1/n)$.
  • Practical Performance: The algorithm demonstrates strong empirical results, outperforming previous solutions on 15 out of 16 benchmark instances, with an average improvement of 2.66%.
  • Efficiency: The algorithm is described as "easy to implement and runs very fast." The experiments show that solving 16 instances took less than 0.1 seconds before local search and under 30 seconds including local search.

Limitations and Future Work

  • Specific Case: The primary theoretical result ($1 + O(1/n)$ approximation) is for the case where $n/2$ is odd. The paper mentions that the algorithm and analysis might differ for the case where $n/2$ is even, which is not the focus here.
  • Local Search: While the paper incorporates a simple local search (swapping teams or super-teams) to further improve solutions, it acknowledges that more complex local search strategies (e.g., involving three or more teams) could potentially yield further improvements, but at a significant increase in running time with diminishing returns.
  • Benchmark Instances: The paper tested on instances where $n \ge 10$ and $n = 2 \pmod 4$. Further exploration on other types of instances or smaller $n$ values could be beneficial.
  • Future Work: The authors suggest exploring more advanced local search techniques and potentially applying their findings to other variants of the Traveling Tournament Problem.

Summary updated

BibTeX
@inproceedings{zhao2021traveling,
  author = {Jingyang Zhao and Mingyu Xiao},
  title = {{The Traveling Tournament Problem with Maximum Tour Length Two: A Practical Algorithm with An Improved Approximation Bound}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/578},
}
Figure