An Improved Approximation Algorithm for the Traveling Tournament Problem

An Improved Approximation Algorithm for the Traveling Tournament Problem

0.00 Avg rating0 Votes
Article ID: iaor201110822
Volume: 61
Issue: 4
Start Page Number: 1077
End Page Number: 1091
Publication Date: Dec 2011
Journal: Algorithmica
Authors: , , ,
Keywords: scheduling, programming: integer, programming: constraints
Abstract:

This paper describes the traveling tournament problem, a well‐known benchmark problem in the field of tournament timetabling. We propose an approximation algorithm for the traveling tournament problem with the constraints such that both the number of consecutive away games and that of consecutive home games are at most k. When k≤5, the approximation ratio of the proposed algorithm is bounded by (2k−1)/k+O(k/n) where n denotes the number of teams; when k>5, the ratio is bounded by (5k−7)/(2k)+O(k/n). For k=3, the most investigated case of the traveling tournament problem to date, the approximation ratio of the proposed algorithm is 5/3+O(1/n); this is better than the previous approximation algorithm proposed for k=3, whose approximation ratio is 2+O(1/n).

Reviews

Required fields are marked *. Your email address will not be published.