The Linear Distance Traveling Tournament Problem Allows an EPTAS

Jingyang Zhao, Mingyu XiaoAAAI 2023 · DOI

TL;DR

This paper introduces a new efficient polynomial-time approximation scheme (EPTAS) for the Linear Distance Traveling Tournament Problem (LDTTP-k). This algorithm significantly improves upon existing approximation ratios, offering a schedule with a total travel distance at most (1 + ε) times the optimal, for any k = o(n) and any ε > 0.

What Problem Does This Paper Address?

The Traveling Tournament Problem (TTP) is a classic scheduling challenge where the goal is to create a sports schedule that minimizes the total travel distance for all teams, subject to constraints like no team playing consecutive home or away games (bounded by k). The Linear Distance Traveling Tournament Problem (LDTTP-k) is a specific variant where all team locations are on a line, simplifying the distance calculations. While TTP is NP-hard, LDTTP-k is also believed to be NP-hard, and finding optimal or near-optimal solutions is computationally challenging. Existing work has provided approximation algorithms for LDTTP-k, but this paper aims to achieve a much stronger theoretical guarantee: an EPTAS, which means the approximation ratio can be made arbitrarily close to 1 by increasing computational effort.

Methods

The authors propose a constructive algorithm that builds a schedule by first partitioning teams and game days into groups. They leverage the concept of a "k-path packing" on a graph representing the teams. The core idea is to arrange "super-games" between groups of teams (super-teams) and then extend these into normal games between individual teams.

Key methodological elements include:

  • Graph Representation: Teams are represented as vertices in a complete graph, with edge weights representing distances. For LDTTP-k, this graph is simplified as teams lie on a line.
  • k-Path Packing: A crucial step involves finding an optimal k-path packing in a subgraph induced by a selected subset of teams ($G_\epsilon$). This packing helps structure the schedule.
  • Super-Teams and Super-Games: Teams are grouped into "super-teams," and a higher-level schedule of "super-games" is constructed. This simplifies the problem by reducing the number of entities to schedule.
  • Hierarchical Scheduling: The algorithm proceeds in stages:
  • Super-game schedule: A schedule for super-games is designed, categorized into "left," "middle," and "right" super-games based on their structure and participants.
  • Extension to path-games: Super-games are extended into "path-games" between groups of teams within the super-teams.
  • Extension to normal games: Path-games are further broken down into individual "normal games" between specific teams.
  • Randomization and Derandomization: The construction involves random labeling of path-teams, which is then derandomized using conditional expectations to achieve a deterministic EPTAS.
  • Handling Unarranged Games: A significant portion of the paper details how to schedule the remaining "unarranged games" that arise from the hierarchical construction, particularly in the "last time slot." This involves decomposing the problem into smaller subproblems and applying existing TTP-2 algorithms.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic construction rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • EPTAS for LDTTP-k: The most significant insight is the demonstration that LDTTP-k, under the condition $k = o(n)$, admits an EPTAS. This is a strong theoretical result, implying that near-optimal schedules can be found efficiently.
  • Hierarchical Scheduling as a General Strategy: The paper showcases the power of a hierarchical approach (super-teams, super-games) to tackle complex scheduling problems. By abstracting and then refining, the problem becomes more manageable.
  • Leveraging k-Path Packings: The optimal k-path packing in a selected subgraph ($G_\epsilon$) is not just a theoretical tool but a structural backbone for constructing the schedule, guiding how teams should interact.
  • The Importance of the Linear Constraint: The linear arrangement of teams in LDTTP-k is exploited to derive specific lower bounds (Lemma 2) and to structure the graph $G_\epsilon$ and its k-path packing.
  • Careful Handling of Unarranged Games: The detailed breakdown of how to schedule the remaining games in the "last time slot" highlights the complexity of ensuring feasibility and minimizing travel distance even after the main structure is in place.

Key Results

  • EPTAS for LDTTP-k: The paper proves that for any $3 \le k = o(n)$, LDTTP-k allows an EPTAS. This means for any $\epsilon > 0$, a schedule can be computed in time $O_\epsilon(1) + n^{o(1)}$ with a total weight at most $(1+\epsilon)$ times the optimal.
  • Improved Approximation Ratio: This result significantly improves upon previous approximation ratios for LDTTP-k.
  • Lower Bounds: The paper establishes two lower bounds for LDTTP-k, which are used to guide the analysis and demonstrate the effectiveness of the proposed algorithm.
  • Feasible Schedule Construction: The paper provides a constructive algorithm that generates a feasible schedule satisfying the TTP-k constraints.

Limitations and Future Work

  • Computational Complexity: While the algorithm is an EPTAS, the $n^{o(1)}$ term in the running time suggests that for very large $n$, the practical performance might still be a concern, although it's significantly better than brute-force. The paper notes that for small $n$, a brute-force approach is suggested, which is not practical.
  • Experimental Performance: The paper focuses on theoretical analysis. The authors suggest that studying the experimental performance of their construction would be a valuable next step.
  • General TTP: The current EPTAS is specific to LDTTP-k. Extending these techniques or developing similar EPTAS for the general TTP (where team locations are not on a line) remains an open challenge.
  • Practicality for Small $n$: The reliance on brute-force for small $n$ indicates a gap in practical applicability for very small instances.

Summary updated

BibTeX
@inproceedings{zhao2023linear,
  author = {Jingyang Zhao and Mingyu Xiao},
  title = {{The Linear Distance Traveling Tournament Problem Allows an EPTAS}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i10.26433},
}
Figure