TY - GEN
T1 - Approximating the traveling tournament problem with maximum tour length 2
AU - Thielen, Clemens
AU - Westphal, Stephan
PY - 2010
Y1 - 2010
N2 - 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 + 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 + 5/n-1.
AB - 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 + 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 + 5/n-1.
KW - approximation algorithm
KW - timetabling
KW - traveling tournament problem
UR - http://www.scopus.com/inward/record.url?scp=78650884686&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-17514-5_26
DO - 10.1007/978-3-642-17514-5_26
M3 - Conference contribution
AN - SCOPUS:78650884686
SN - 3642175163
SN - 9783642175169
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 303
EP - 314
BT - Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings
T2 - 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010
Y2 - 15 December 2010 through 17 December 2010
ER -