This paper introduces and studies the p-partite Traveling Tournament Problem (p-partite TTP), a generalization of the Bipartite Traveling Tournament Problem (BTTP), where pn teams are divided into p leagues. The core idea is a TSP-based algorithm that constructs feasible tournament schedules by first creating a single round-robin (SRR) tournament for "super-teams" (leagues) and then extending these into "regular-games" between individual teams. The paper proves that the p-partite TTP is NP-hard for any fixed p >= 3 and demonstrates that the proposed algorithm achieves an approximation ratio of 8/3 + O(1/n) for p = 3. Empirically, the algorithm produces practical schedules with significantly reduced total travel distances, highlighting its effectiveness in generating high-quality multipartite tournament schedules.
Problem
The paper addresses the following bottlenecks and challenges:
Generalizing Traveling Tournament Problem (TTP) to multiple leagues: Existing TTP variants primarily focus on two-conference structures (Bipartite TTP or BTTP), but many professional sports leagues use three or more conferences/divisions. The p-partite TTP is introduced to model this more general scenario.
NP-hardness of p-partite TTP: The p-partite TTP is a challenging optimization problem, proven to be NP-hard for any fixed p >= 3. Constructing even a simple feasible schedule is non-trivial.
Minimizing total travel distance under constraints: The objective is to find a distance-optimal double round-robin (DRR) p-partite tournament that minimizes total travel cost while satisfying "no-repeat" (no team pair plays consecutive games) and "at-most-three" (each team plays at most three consecutive home or away games) constraints.
Lack of efficient algorithms for p-partite TTP: While TSP-based methods exist for standard TTP, extending them to the p-partite TTP, even for p = 3, is non-trivial.
Key Contributions
Initiates the study of the p-partite Traveling Tournament Problem (p-partite TTP).
Proves that the p-partite TTP is NP-hard for any fixed p >= 3.
Proposes an efficient algorithm based on the Traveling Salesman Problem (TSP) that applies to any fixed p >= 2.
Proves that the algorithm achieves an approximation ratio of 8/3 + O(1/n) for the 3-partite TTP.
Demonstrates through experiments that the algorithm delivers excellent empirical performance, producing high-quality tournament schedules with significantly reduced total travel distances in practice.
Method
The proposed method constructs a feasible solution for the p-partite TTP using a TSP-based approach.
Overall Flow:
Super-team Abstraction: Each league X_i is treated as a "super-team". Individual teams within a league are "regular-teams".
SRR Tournament for Super-teams: A single round-robin (SRR) tournament is designed for the p super-teams. This tournament spans p-1 time slots. In each time slot, p/2 super-games are scheduled, including one "left" super-game and p/2 - 1 "normal" super-games. The construction varies based on whether p is even or odd.
Case where p is Even: The SRR tournament is directly constructed for the p super-teams.
Case where p is Odd: n is assumed to be even. Each league X_i is transformed into two disjoint "half-leagues" X_i^a and X_i^b of size n/2. These 2p half-leagues are then treated as super-teams, making the number of super-teams even. An SRR tournament is designed for these 2p super-teams, avoiding super-games between half-leagues originating from the same original league.
Extension of Super-games to Regular-games: Once the SRR tournament for super-teams is established, each super-game (normal or left) is extended into regular-games played between individual regular-teams. This extension depends on n mod 3.
Normal Super-games X_i -> X_j: Given TSP cycles T_{X_i} and T_{X_j} for leagues X_i and X_j, regular-game sets m_k are defined as {x_{i'} -> y_{(i'+k) mod n}}_{i'=0}^{n-1}. Blocks of regular-games M_k are defined as M_k M_{3k-3} M_{3k-2} M_{3k-1} M_{3k-3} M_{3k-2} M_{3k-1}. The scheduling of U_k (m_k U M_k) varies based on n mod 3.
Left Super-games X_i <- X_j: Similar regular-game sets m_k and M_k are defined, and scheduling also varies based on n mod 3. The design ensures that a team's home/away status switches after a left super-game.
Key Equations:
The paper defines regular-game sets m_k for normal super-games X_i -> X_j as:
m_k = {x_{i'} -> y_{(i'+k) mod n}}_{i'=0}^{n-1}
The set of regular-games with reversed venues M_k is defined as:
M_k = {x_{i'} <- y_{(i'+k) mod n}}_{i'=0}^{n-1}
A block of regular-games played over 6 consecutive days between all regular-teams in X_i U X_j is defined as:
M_k M_{3k-3} M_{3k-2} M_{3k-1} M_{3k-3} M_{3k-2} M_{3k-1}
Technical Details
Graph Representation: The input is a complete graph G = (V, E) where V consists of pn teams partitioned into p pairwise disjoint n-team leagues X = {X_1, ..., X_p}. Distances c(x, y) between home venues are assumed to be a metric.
Objective: Minimize the total travel cost incurred by all teams.
Constraints:
No-repeat constraint: No team pair plays consecutive games.
At-most-three constraint: Each team plays at most three consecutive home or away games.
TSP Cycle Computation:
For each league X_i, a TSP cycle T_{X_i} in G[X_i] is computed.
Initially, a TSP cycle T_{X_i} in G[X_i U {x*}] is computed using the Christofides algorithm (Christofides 2022), where x* is chosen from X_i to minimize the cost of T_{X_i}. x* is then removed to obtain T_{X_i} in G[X_i].
When p is odd, T_{X_i} is further transformed into two disjoint cycles T_{X_i}^a and T_{X_i}^b of size n/2. This involves deleting edges x_{i'} x_{i'+1} and x_{i'+n/2} x_{i'+1+n/2} and adding x_{i'} x_{i'+1+n/2} and x_{i'+1} x_{i'+n/2}. The choice of i* minimizes c(T_{X_i}^a(i*)) + c(T_{X_i}^b(i*)).
Optimization (Experimental): Instead of Alg. 1 (which uses Christofides' algorithm), the well-known 2-opt heuristic is used for TSP cycle computation in experiments due to its simplicity and better practical solutions.
Heuristic Enhancements (Experimental):
The two modifications described in Remark 2 are applied to replace "left" super-games with "normal" super-games if they incur smaller travel costs.
When labeling (half-)leagues as super-teams, all possible labelings are considered, and the best solution found is returned. For p even, p! labelings; for p odd, 2^p p! labelings.
Implementation Details:
Implemented in C++.
Executed on a desktop computer with an AMD Ryzen 5 PRO 4650G with Radeon Graphics (3.7 GHz, 32 GB RAM).
All instances are solved within 0.8s overall.
Results
Datasets:
Adapted TTP benchmark instances (Trick 2025; Bulck et al. 2020).
Instance sets: GAL (derived from 3D locations of exoplanets), NFL, NL (National League of Major League Baseball), SUP (Super 14 Rugby cup), and BRA (Brazilian soccer championship).
Instances where N mod p = 0 and n >= 2 for p even.
Instances where N mod 2p = 0 and n >= 2 for p odd.
Number of Instances Tested:
p = 2: 42 instances
p = 3: 10 instances
p = 4: 20 instances
Metrics: Approximation gap to the Independent Lower Bound (ILB). Gap (%) = (Result - ILB) / ILB.
Baselines:
Independent Lower Bound (ILB) (Easton, Nemhauser, and Trick 2002; Urrutia, Ribeiro, and Melo 2007).
Previous algorithm for p = 2 when n mod 3 = 0 (Hoshino and Kawarabayashi 2013).
Numeric Results:
Approximation Ratio (Theoretical): min{(p+5)/3 + 12/n, 3} for p >= 2. For p = 3, 8/3 + O(1/n).
Average Gaps (Our Algorithm):
p = 2: 10.23%
p = 3: 32.97%
p = 4: 35.60%
Specific Gaps (Our Algorithm):
p = 2: falls within 5% - 10% for most instances.
p = 3: does not exceed 70% for any tested instance.
p = 4: lies within 35% - 45% for most instances.
Comparison with Baseline for p = 2, n mod 3 = 0:
Our algorithm: 6.92% gap.
Previous algorithm (Hoshino and Kawarabayashi 2013): 5.52% gap.
Runtime/Training Cost: All instances are solved together within 0.8s overall.
Weaknesses / Limitations
Intra-league Property: When p > 2, the schedule satisfies an intra-league property where opponents for consecutive away games are from the same league. This may be a limitation, as an optimal solution might achieve smaller travel costs by playing consecutive away games against opponents from different leagues. It remains unknown how to construct a high-quality schedule that does not rely on this property for p > 2.
Theoretical Approximation Barrier: It remains an open question whether the 3-approximation barrier can be broken for any fixed p > 3.
Hardness of Approximation: It is worthwhile to explore the hardness of approximation, such as establishing APX-hardness for the p-partite TTP.
Evidence
Method evidence: "In this paper, we initiate the study of the p-partite Traveling Tournament Problem (p-partite TTP) and prove that it is NP-hard for any fixed p > 3. We then focus on designing effective algorithms for the p-partite TTP. Constructing even a simple feasible schedule for the p-partite TTP is non-trivial. To address this, we propose an approach based on the Traveling Salesman Problem (TSP) that applies to any fixed p > 2." (section: Our Contributions)
Result evidence: "We observe that for the case p = 2, the gap of our results falls within 5% - 10% for most instances; for p = 3, the gap does not exceed 70% for any tested instance; and for p = 4, the gap lies within 35% – 45% for most instances. Note that our algorithm has a slightly larger gap on the SUP set, where the total number of teams N is small. We further remark that the average gaps for our algorithm are 10.23%, 32.97%, and 35.60% for p = 2, 3, 4, respectively." (section: Experimental Results)
Limitation evidence: "Remark 1. When p > 2, our schedule satisfies the intra-league property: when a regular-team plays two or three consecutive away regular-games, its opponents are from the same league, say Xi, and the locations of these opponents appear consecutively along a cycle in G[Xi]. This property may be a limitation, as in an optimal solution to the p-partite TTP, a regular-team may achieve a much smaller travel cost by playing consecutive away regular-games against opponents from different leagues (see Fig. 4). Currently, it remains unknown how to construct a high-quality schedule that does not rely on the intra-league property for p > 2." (section: Performance of the Schedule)
Additional Figures
Figure 1: The six divisions of the NBA, where each division consists of 5 teams. teams in the NBA are divided into six divisions of 5 teams each, and the 32 teams in the NFL are divided into eight di-
Figure 2: The SRR tournament in the 1st time slot (p = 10).
Figure 3: The SRR tournament in the 2nd time slot (p = 10).
Figure 4: An illustration of the intra-league property, where vertices (regular-teams) in the same league share the same color: whenever the black vertex plays three consecutive away regular-games, its opponents are from the same league (resp., different leagues) in our (resp., an optimal) solution.
Fig. 5 summarizes our results, showing the approxima- tion gaps of our algorithm for the p-partite TTP with p = 2, 3, 4, alongside the previous algorithm in (Hoshino and Kawarabayashi 2013), which applies only to p = 2 with n mod 3 = 0. The vertical axis lists instances, and the hori-