.png){kind=icon}
.png){kind=icon}
Return
An approximation algorithm for the traveling tournament problem
.png){kind=icon}
PRE
AI
DOI：10.1007/s10479-010-0742-x.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper describes the traveling tournament problem, a well-known benchmark problem in the field of tournament timetabling. We propose a new lower bound for the traveling tournament problem, and construct a randomized approximation algorithm yielding a feasible solution whose approximation ratio is less than 2+(9/4)/(n-1), where n is the number of teams. Additionally, we propose a deterministic approximation algorithm with the same approximation ratio using a derandomization technique. For the traveling tournament problem, the proposed algorithms are the first approximation algorithms with a constant approximation ratio, which is less than 2+3/4.
Keywords:
Traveling tournament problem
Lower bound
Approximation algorithm
Tournament
Timetabling
Scheduling
Journal
IF:
4.5
Papers:
8.0K
Citations:
2.1W