Approximation algorithms for TTP(2)

Clemens Thielen, Stephan Westphal

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

We consider the traveling tournament problem, which is a well-known benchmark problem in tournament timetabling. It consists of designing a schedule for a sports league of n teams such that the total traveling costs of the teams are minimized. The most important variant of the traveling tournament 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 two approximation algorithms for the problem. The first algorithm has an approximation ratio of 3/2 + 6/n-4 in the case that n/2 is odd, and of 3/2 + 5/n-1 in the case that n/2 is even. Furthermore, we show that this algorithm is applicable to real world problems as it yields close to optimal tournaments for many standard benchmark instances. The second algorithm we propose is only suitable for the case that n/2 is even and n ≥ 12, and achieves an approximation ratio of 1 + 16/n in this case, which makes it the first 1 + O(1/n)-approximation for the problem.

Original languageEnglish
Pages (from-to)1-20
Number of pages20
JournalMathematical Methods of Operations Research
Volume76
Issue number1
DOIs
StatePublished - Aug 2012
Externally publishedYes

Keywords

  • Approximation algorithms
  • Sports scheduling
  • Timetabling
  • Traveling tournament problem

Fingerprint

Dive into the research topics of 'Approximation algorithms for TTP(2)'. Together they form a unique fingerprint.

Cite this