Complexity of the traveling tournament problem
We consider the complexity of the traveling tournament problem, which is a well-known benchmark problem in tournament timetabling. The problem was supposed to be computationally hard ever since its proposal in 2001. Recently, the first NP-completeness proof has been given for the variant of the problem were no constraints on the number of consecutive home games or away games of a team are considered. The complexity of the original traveling tournament problem including these constraints, however, is still open. In this paper, we show that this variant of the problem is strongly NP-complete when the upper bound on the maximal number of consecutive away games is set to 3. (c) 2010 Elsevier B.V. All rights reserved.
traveling tournament problem timetabling scheduling computational complexity