Research map / Learning theory and algorithms / Submodular and game algorithms
A Matching-Based Algorithm for the Traveling Tournament Problem
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a minimum-weight-matching-based construction with randomized labeling for TTP-4, giving a 1.625+ε approximation (improving 1.7+ε) and improving best-known results on 9 benchmark instances by 6.65% on average.
Problem
Traveling Tournament Problem with at-most-4 consecutive home/away constraint (TTP-4): design a feasible double round-robin schedule minimizing total travel distance.
Approach
Pack teams into super-teams formed from two minimum-weight-matching edges (instead of 4-cycles) so that almost every team plays 4 consecutive away games along two matching edges; add two new lower bounds tied to the matching and a uniformly random labeling of matching edges to get a simpler analysis and a 1.625+ε approximation.
Key results
- Achieves a randomized (1.625+ε)-approximation for TTP-4, improving the previous 1.7+ε bound.
- Improves best-known results on all 9 benchmark instances with n ≡ 0 (mod 8), with an average improvement of 6.65% (e.g., NL16 from 263745 to 229301, 13.06%).
- All nine instances solved together within 9.55 seconds on a standard desktop.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the prior construction with a minimum-weight-matching-based construction | TTP-4 approximation algorithm · TTP-4 | approximation ratio: 1.7 + ε -> 1.625+ε | Helped |
| Use the matching-based algorithm with pair-wise swapping local search | TTP-4 benchmark instances where n ≡ 0 (mod 8) · 9 benchmark instances | improvement ratio: average improvement ratio of 6.65% | Helped |
| Use the matching-based algorithm with pair-wise swapping local search | Galaxy40 · Galaxy40 | traveling cost: 216863 -> 212680; 1.93% | Helped |
| Use the matching-based algorithm with pair-wise swapping local search | Galaxy32 · Galaxy32 | traveling cost: 104433 -> 103054; 1.32% | Helped |
| Use the matching-based algorithm with pair-wise swapping local search | Galaxy24 · Galaxy24 | traveling cost: 40832 -> 39453; 3.38% | Helped |
| Use the matching-based algorithm with pair-wise swapping local search | Galaxy16 · Galaxy16 | traveling cost: 14365 -> 13188; 8.19% | Helped |
| Use the matching-based algorithm with pair-wise swapping local search | NFL32 · NFL32 | traveling cost: 809725 -> 779620; 3.72% | Helped |
| Use the matching-based algorithm with pair-wise swapping local search | NFL24 · NFL24 | traveling cost: 436531 -> 403660; 7.53% | Helped |
| Use the matching-based algorithm with pair-wise swapping local search | NFL16 · NFL16 | traveling cost: 235936 -> 213649; 9.45% | Helped |
| Use the matching-based algorithm with pair-wise swapping local search | NL16 · NL16 | traveling cost: 263745 -> 229301; 13.06% | Helped |
| Use the matching-based algorithm with pair-wise swapping local search | Brazil24 · Brazil24 | traveling cost: 464921 -> 412399; 11.30% | Helped |
Limitations
- Approach only improves the approximation ratio for k=4; for k>4 the bound worsens and for k=2,3 other methods are better.
- Experiments focus on the n ≡ 0 (mod 8) case; other cases need additional right super-games not fully implemented.
- Relies on existing benchmark instances, with a practical pipeline that adds a local search (pair-wise swapping) to the construction.
Experimental setup
Datasets: TTP benchmark instances (Trick 2024 website), 9 instances with n divisible by 8
Benchmarks: Galaxy40 Galaxy32 Galaxy24 Galaxy16 NFL32 NFL24 NFL16 NL16 Brazil24
Metrics: total travel distance improvement ratio over best-known approximation ratio
Baselines: Westphal and Noparlik 2014 best-known results Zhao, Xiao, and Xu 2022 1.7-approximation
Builds on: packing-and-extending technique for TTP-k Zhao, Xiao and Xu 2022 4-cycle based 1.7-approximation Westphal and Noparlik 2014 Hamiltonian cycle and LKH approach
Closest papers by meaning
- The Linear Distance Traveling Tournament Problem Allows an EPTAS (AAAI 2023 · similarity 0.95)
- A TSP-Based Algorithm for Multi-League Traveling Tournament (AAAI 2026 · similarity 0.93)
- A Recursive Algorithm to Generate Balanced Weekend Tournaments (AAAI 2018 · similarity 0.88)
- An Exercise in Tournament Design: When Some Matches Must Be Scheduled (AAAI 2024 · similarity 0.86)
- Adaptive Manipulation for Coalitions in Knockout Tournaments (AAAI 2025 · similarity 0.84)
- Improved Approximation Algorithms for Clustered TSP and Subgroup Planning (AAAI 2025 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.