Approximating the Traveling Tournament Problem with Maximum Tour Length 2

摘要

We consider the traveling tournament problem, which is a well-known benchmark problem in tournament timetabling. The most important variant of the problem imposes restrictions on the number of consecutive home games or away games a team may have. We consider the case where at most two consecutive home games or away games are allowed. We show that the well-known independent lower bound for this case cannot be reached and present an approximation algorithm that has an approximation ratio of 3/2 + 6/ n-4 . where n is the number of teams in the tournament. In the case that n is divisible by 4, this approximation ratio improves to 3/2 + 5/ n-1.