An approximation algorithm for the traveling tournament problem

This paper describes the traveling tournament problem, a well‐known benchmark problem in the field of tournament timetabling. We propose a new lower bound for the traveling tournament problem, and construct a randomized approximation algorithm yielding a feasible solution whose approximation ratio is less than 2+(9/4)/(n-1), where n is the number of teams. Additionally, we propose a deterministic approximation algorithm with the same approximation ratio using a derandomization technique. For the traveling tournament problem, the proposed algorithms are the first approximation algorithms with a constant approximation ratio, which is less than 2+3/4.