Generating Approximate Solutions to the TTP using a Linear Distance
  Relaxation
  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.
