2010 | OriginalPaper | Buchkapitel
Approximating the Traveling Tournament Problem with Maximum Tour Length 2
Erschienen in: Algorithms and Computation
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider the traveling tournament problem, which is a well-known benchmark problem in tournament timetabling. The most important variant of the problem imposes restrictions on the number of consecutive home games or away games a team may have. We consider the case where at most two consecutive home games or away games are allowed. We show that the well-known independent lower bound for this case cannot be reached and present an approximation algorithm that has an approximation ratio of
$3/2+\frac{6}{n-4}$
, where
n
is the number of teams in the tournament. In the case that
n
is divisible by 4, this approximation ratio improves to
$3/2+\frac{5}{n-1}$
.