The APX-hardness of the Traveling Tournament Problem

The Traveling Tournament Problem (TTP-$k$) is a well-known benchmark problem in sports scheduling, which asks us to design a double round-robin schedule such that each pair of teams plays one game in each other's home venue, each team plays at most $k$-consecutive home games or away games, and the total traveling distance of all the $n$ teams is minimized. TTP-$k$ allows a PTAS when $k=2$ and becomes APX-hard when $k\geq n-1$. In this paper, we reduce the gap by showing that TTP-$k$ is APX-hard for any fixed $k\geq3$.