A Further Improvement on Approximating TTP-2

The Traveling Tournament Problem (TTP) is a hard but interesting sports scheduling problem inspired by Major League Baseball, which is to design a double round-robin schedule such that each pair of teams plays one game in each other’s home venue, minimizing the total distance traveled by all $n$ teams ($n$ is even). In this paper, we consider TTP-2, i.e., TTP with one more constraint that each team can have at most two consecutive home games or away games. Due to the different structural properties, known algorithms for TTP-2 are different for $n\mathrm{/}2$ being odd and even. For odd $n\mathrm{/}2$, the best known approximation ratio is about $(1+12\mathrm{/}n)$, and for even $n\mathrm{/}2$, the best known approximation ratio is about $(1+4\mathrm{/}n)$. In this paper, we further improve the approximation ratio from $(1+4\mathrm{/}n)$ to $(1+3\mathrm{/}n)$ for $n\mathrm{/}2$ being even. Experimental results on benchmark sets show that our algorithm can improve previous results on all instances with even $n\mathrm{/}2$ by $1\mathrm{\%}$ to $4\mathrm{\%}$.