License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2022.83
URN: urn:nbn:de:0030-drops-168813
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16881/
Go to the corresponding LIPIcs Volume Portal

Zhao, Jingyang ; Xiao, Mingyu ; Xu, Chao

Improved Approximation Algorithms for the Traveling Tournament Problem

pdf-format:
LIPIcs-MFCS-2022-83.pdf (0.7 MB)

Abstract

The Traveling Tournament Problem (TTP) is a well-known benchmark problem in the field of tournament timetabling, which asks us to design a double round-robin schedule such that each pair of teams plays one game in each other’s home venue, minimizing the total distance traveled by all n teams (n is even). TTP-k is the problem with one more constraint that each team can have at most k consecutive home games or away games. The case where k = 3, TTP-3, is one of the most investigated cases. In this paper, we improve the approximation ratio of TTP-3 from (1.667+ε) to (1.598+ε), for any ε > 0. Previous schedules were constructed based on a Hamiltonian cycle of the graph. We propose a novel construction based on triangle packing. Then, by combining our triangle packing schedule with the Hamiltonian cycle schedule, we obtain the improved approximation ratio. The idea of our construction can also be extended to k ≥ 4. We demonstrate that the approximation ratio of TTP-4 can be improved from (1.750+ε) to (1.700+ε) by the same method. As an additional product, we also improve the approximation ratio of LDTTP-3 (TTP-3 where all teams are allocated on a straight line) from 4/3 to (6/5+ε).

BibTeX - Entry

@InProceedings{zhao_et_al:LIPIcs.MFCS.2022.83,
  author =	{Zhao, Jingyang and Xiao, Mingyu and Xu, Chao},
  title =	{{Improved Approximation Algorithms for the Traveling Tournament Problem}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{83:1--83:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16881},
  URN =		{urn:nbn:de:0030-drops-168813},
  doi =		{10.4230/LIPIcs.MFCS.2022.83},
  annote =	{Keywords: Sports scheduling, Traveling Tournament Problem, Approximation algorithm}
}

Keywords: Sports scheduling, Traveling Tournament Problem, Approximation algorithm
Collection: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Issue Date: 2022
Date of publication: 22.08.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI