A 5.875-approximation for the Traveling Tournament Problem
In this paper we propose an approximation for the Traveling Tournament Problem which is the problem of designing a schedule for a sports league consisting of a set of teams T such that the total traveling costs of the teams are minimized. It is not allowed for any team to have more than k home-games or k away-games in a row. We propose an algorithm which approximates the optimal solution by a factor of 2+2k/n+k/(n?1)+3/n+3/(2?k) which is not more than 5.875 for any choice of k?4 and n?6. This is the first constant factor approximation for k>3.
traveling tournament problem sports scheduling approximation algorithms