Approximation algorithms for TTP(2)

摘要

We consider the traveling tournament problem, which is a well-known benchmark problem in tournament timetabling. It consists of designing a schedule for a sports league of n teams such that the total traveling costs of the teams are minimized. The most important variant of the traveling tournament 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 two approximation algorithms for the problem. The first algorithm has an approximation ratio of 3/2 + 6-4 in the case that n/2 is odd, and of 3/2 + 5-1 in the case that n/2 is even. Furthermore, we show that this algorithm is applicable to real world problems as it yields close to optimal tournaments for many standard benchmark instances. The second algorithm we propose is only suitable for the case that n/2 is even and n ≥ 12, and achieves an approximation ratio of 1 + 16 in this case, which makes it the first 1 + O(1)-approximation for the problem.