Approximating the traveling tournament problem with maximum tour length 2

Clemens Thielen; Stephan Westphal

doi:10.1007/978-3-642-17514-5_26

Approximating the traveling tournament problem with maximum tour length 2

Clemens Thielen, Stephan Westphal

University of Kaiserslautern

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Scopus citations

Abstract

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.

Original language	English
Title of host publication	Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings
Pages	303-314
Number of pages	12
Edition	PART 2
DOIs	https://doi.org/10.1007/978-3-642-17514-5_26
State	Published - 2010
Externally published	Yes
Event	21st Annual International Symposium on Algorithms and Computations, ISAAC 2010 - Jeju Island, Korea, Republic of Duration: 15 Dec 2010 → 17 Dec 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 2
Volume	6507 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	21st Annual International Symposium on Algorithms and Computations, ISAAC 2010
Country/Territory	Korea, Republic of
City	Jeju Island
Period	15/12/10 → 17/12/10

Keywords

approximation algorithm
timetabling
traveling tournament problem

Access to Document

10.1007/978-3-642-17514-5_26

Cite this

Thielen, C., & Westphal, S. (2010). Approximating the traveling tournament problem with maximum tour length 2. In Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings (PART 2 ed., pp. 303-314). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6507 LNCS, No. PART 2). https://doi.org/10.1007/978-3-642-17514-5_26

Thielen, Clemens ; Westphal, Stephan. / Approximating the traveling tournament problem with maximum tour length 2. Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 2. ed. 2010. pp. 303-314 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2).

@inproceedings{807e853b764e49db97fa64daaeef997c,

title = "Approximating the traveling tournament problem with maximum tour length 2",

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

keywords = "approximation algorithm, timetabling, traveling tournament problem",

author = "Clemens Thielen and Stephan Westphal",

year = "2010",

doi = "10.1007/978-3-642-17514-5_26",

language = "English",

isbn = "3642175163",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 2",

pages = "303--314",

booktitle = "Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings",

edition = "PART 2",

note = "21st Annual International Symposium on Algorithms and Computations, ISAAC 2010 ; Conference date: 15-12-2010 Through 17-12-2010",

}

Thielen, C & Westphal, S 2010, Approximating the traveling tournament problem with maximum tour length 2. in Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 2 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 2, vol. 6507 LNCS, pp. 303-314, 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010, Jeju Island, Korea, Republic of, 15/12/10. https://doi.org/10.1007/978-3-642-17514-5_26

Approximating the traveling tournament problem with maximum tour length 2. / Thielen, Clemens; Westphal, Stephan.
Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 2. ed. 2010. p. 303-314 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6507 LNCS, No. PART 2).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 -

Thielen C, Westphal S. Approximating the traveling tournament problem with maximum tour length 2. In Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 2 ed. 2010. p. 303-314. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2). doi: 10.1007/978-3-642-17514-5_26

Approximating the traveling tournament problem with maximum tour length 2

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this