A Matching-Based Algorithm for the Traveling Tournament Problem

Abstract

The Traveling Tournament Problem (TTP-k) is a well-known benchmark problem in tournament timetabling. It involves designing a feasible double round-robin tournament for a sports league of n teams under several feasibility requirements, while minimizing the total traveling costs of the teams. The parameter k requires that in the tournament at most k consecutive home games or away games for each team are allowed. TTP-k with a small k, especially for k=2,3 and 4, have been extensively studied in the literature. In this paper, we focus on TTP-4 and design an efficient algorithm for it based on minimum weight matching. In theory, we prove that our algorithm has an approximation ratio of 1.625+ε for any constant ε>0, improving the best-known approximation ratio of 1.7+ε. In practice, our experimental results indicate an average improvement of 6.65% over the best-known solutions on 9 benchmark instances.