The Linear Distance Traveling Tournament Problem Allows an EPTAS

Abstract

The Traveling Tournament Problem (TTP-k) is a well-known benchmark problem in tournament timetabling and has been extensively studied in the field of AI. In this problem, we are going to design a double round-robin schedule such that each pair of teams plays one game in each other's home venue, minimizing the total distance traveled by all n teams (n is even) under the constraint that each team can have at most k-consecutive home games or away games. The Linear Distance Traveling Tournament Problem (LDTTP-k), where all teams are located on a line, was introduced by Hoshino and Kawarabayashi (AAAI 2012). For LDTTP-3, they gave a 4/3-approximation algorithm for n≡4 (mod 6) teams. In this paper, we show that for any 3≤k=o(∛n), LDTTP-k allows an efficient polynomial-time approximation scheme (EPTAS).