  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/2$ being odd and even. For odd $n/2$, the best known
approximation ratio is about $(1+12/n)$, and for even $n/2$, the best known
approximation ratio is about $(1+4/n)$. In this paper, we further improve the
approximation ratio from $(1+4/n)$ to $(1+3/n)$ for $n/2$ being even.
Experimental results on benchmark sets show that our algorithm can improve
previous results on all instances with even $n/2$ by $1\%$ to $4\%$.

Data Structures and Algorithms