Complexity of the traveling tournament problem

Clemens Thielen; Stephan Westphal

doi:10.1016/j.tcs.2010.10.001

Complexity of the traveling tournament problem

Clemens Thielen, Stephan Westphal

University of Kaiserslautern

Research output: Contribution to journal › Article › peer-review

54 Scopus citations

Abstract

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.

Original language	English
Pages (from-to)	345-351
Number of pages	7
Journal	Theoretical Computer Science
Volume	412
Issue number	4-5
DOIs	https://doi.org/10.1016/j.tcs.2010.10.001
State	Published - 4 Feb 2011
Externally published	Yes

Keywords

Computational complexity
Scheduling
Timetabling
Traveling tournament problem

Access to Document

10.1016/j.tcs.2010.10.001

Cite this

@article{34b96c50f1a749dbbfe3ddfef1dcd9b7,

title = "Complexity of the traveling tournament problem",

abstract = "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.",

keywords = "Computational complexity, Scheduling, Timetabling, Traveling tournament problem",

author = "Clemens Thielen and Stephan Westphal",

year = "2011",

month = feb,

day = "4",

doi = "10.1016/j.tcs.2010.10.001",

language = "English",

volume = "412",

pages = "345--351",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "4-5",

}

TY - JOUR

T1 - Complexity of the traveling tournament problem

AU - Thielen, Clemens

AU - Westphal, Stephan

PY - 2011/2/4

Y1 - 2011/2/4

N2 - 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.

AB - 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.

KW - Computational complexity

KW - Scheduling

KW - Timetabling

KW - Traveling tournament problem

UR - http://www.scopus.com/inward/record.url?scp=78650827038&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2010.10.001

DO - 10.1016/j.tcs.2010.10.001

M3 - Article

AN - SCOPUS:78650827038

SN - 0304-3975

VL - 412

SP - 345

EP - 351

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 4-5

ER -

Complexity of the traveling tournament problem

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this