1 Search Results for "Kou, Shaowei"

Document
DOI: 10.4230/LIPIcs.MFCS.2016.89
An Improved Approximation Algorithm for the Traveling Tournament Problem with Maximum Trip Length Two

Authors: Mingyu Xiao and Shaowei Kou

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
The Traveling Tournament Problem is a complex combinatorial optimization problem in tournament timetabling, which asks a schedule of home/away games meeting specific feasibility requirements, while also minimizing the total distance traveled by all the n teams (n is even). Despite intensive algorithmic research on this problem over the last decade, most instances with more than 10 teams in well-known benchmarks are still unsolved. In this paper, we give a practical approximation algorithm for the problem with constraints such that at most two consecutive home games or away games are allowed. Our algorithm, that generates feasible schedules based on minimum perfect matchings in the underlying graph, not only improves the previous approximation ratio from (1+16/n) to about (1+4/n) but also has very good experimental performances. By applying our schedules on known benchmark sets, we can beat all previously-known results of instances with n being a multiple of 4 by 3% to 10%.
Cite as

Mingyu Xiao and Shaowei Kou. An Improved Approximation Algorithm for the Traveling Tournament Problem with Maximum Trip Length Two. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 89:1-89:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{xiao_et_al:LIPIcs.MFCS.2016.89,
  author =	{Xiao, Mingyu and Kou, Shaowei},
  title =	{{An Improved Approximation Algorithm for the Traveling Tournament Problem with Maximum Trip Length Two}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{89:1--89:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.89},
  URN =		{urn:nbn:de:0030-drops-64976},
  doi =		{10.4230/LIPIcs.MFCS.2016.89},
  annote =	{Keywords: sports scheduling, traveling tournament problem, approximation algorithms, timetabling combinatorial optimization}
}
  • Refine by Author
  • 1 Kou, Shaowei
  • 1 Xiao, Mingyu

  • Refine by Classification

  • Refine by Keyword
  • 1 approximation algorithms
  • 1 sports scheduling
  • 1 timetabling combinatorial optimization
  • 1 traveling tournament problem

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact