Generating approximate solutions to the TTP using a linear distance relaxation

DOI10.1613/JAIR.3713MaRDI QIDQ3143573zbMATH OpenOpenAlexFDO

Authors Richard Hoshino, Ken-ichi Kawarabayashi

Publication date 3 December 2012

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.6049

zbMATH Keywords

\(n\)-team traveling tournament problemapproximate solutionsports scheduling

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Abstract: In some domestic professional sports leagues, the home stadiums are located in cities connected by a common train line running in one direction. For these instances, we can incorporate this geographical information to determine optimal or nearly-optimal solutions to the n-team Traveling Tournament Problem (TTP), an NP-hard sports scheduling problem whose solution is a double round-robin tournament schedule that minimizes the sum total of distances traveled by all n teams. We introduce the Linear Distance Traveling Tournament Problem (LD-TTP), and solve it for n=4 and n=6, generating the complete set of possible solutions through elementary combinatorial techniques. For larger n, we propose a novel "expander construction" that generates an approximate solution to the LD-TTP. For n congruent to 4 modulo 6, we show that our expander construction produces a feasible double round-robin tournament schedule whose total distance is guaranteed to be no worse than 4/3 times the optimal solution, regardless of where the n teams are located. This 4/3-approximation for the LD-TTP is stronger than the currently best-known ratio of 5/3 + epsilon for the general TTP. We conclude the paper by applying this linear distance relaxation to general (non-linear) n-team TTP instances, where we develop fast approximate solutions by simply "assuming" the n teams lie on a straight line and solving the modified problem. We show that this technique surprisingly generates the distance-optimal tournament on all benchmark sets on 6 teams, as well as close-to-optimal schedules for larger n, even when the teams are located around a circle or positioned in three-dimensional space.

Recommendations

• Approximation algorithms for \(\mathrm{TTP(2)}\)
• A 5.875-approximation for the traveling tournament problem
• An approximation algorithm for the bipartite traveling tournament problem
• Approximating the traveling tournament problem with maximum tour length 2
• The timetable constrained distance minimization problem

Cited in

(5)

• A new branch-and-price algorithm for the traveling tournament problem
• A polyhedral study for the cubic formulation of the unconstrained traveling tournament problem
• A multi-round generalization of the traveling tournament problem and its application to Japanese baseball
• The APX-hardness of the traveling tournament problem
• A 5-approximation algorithm for the traveling tournament problem

This page was built for publication: Generating approximate solutions to the TTP using a linear distance relaxation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3143573)