Document Open Access Logo

An Improved Approximation Algorithm for the Traveling Tournament Problem with Maximum Trip Length Two

Authors Mingyu Xiao, Shaowei Kou

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.89.pdf
  • Filesize: 0.57 MB
  • 14 pages

Document Identifiers

Author Details

Mingyu Xiao
Shaowei Kou

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.MFCS.2016.89

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

Subject Classification

Keywords
  • sports scheduling
  • traveling tournament problem
  • approximation algorithms
  • timetabling combinatorial optimization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Aris Anagnostopoulos, Laurent Michel, Pascal Van Hentenryck, and Yannis Vergados. A simulated annealing approach to the traveling tournament problem. Journal of Scheduling, 9(2):177-193, 2006. Google Scholar
  2. Rishiraj Bhattacharyya. A note on complexity of traveling tournament problem. Optimization Online, 2009. Google Scholar
  3. Robert Thomas Campbell and DS Chen. A minimum distance basketball scheduling problem. Management science in sports, 4:15-26, 1976. Google Scholar
  4. Dominique de Werra. Some models of graphs for scheduling sports competitions. Discrete Applied Mathematics, 21(1):47-65, 1988. Google Scholar
  5. Luca Di Gaspero and Andrea Schaerf. A composite-neighborhood tabu search approach to the traveling tournament problem. Journal of Heuristics, 13(2):189-207, 2007. Google Scholar
  6. Kelly Easton, George Nemhauser, and Michael Trick. The traveling tournament problem: description and benchmarks. In 7th International Conference on Principles and Practice of Constraint Programming, pages 580-584, 2001. Google Scholar
  7. Kelly Easton, George Nemhauser, and Michael Trick. Solving the travelling tournament problem: a combined integer programming and constraint programming approach. In 4th International Conference of Practice and Theory of Automated Timetabling IV, pages 100-109, 2003. Google Scholar
  8. Nobutomo Fujiwara, Shinji Imahori, Tomomi Matsui, and Ryuhei Miyashiro. Constructive algorithms for the constant distance traveling tournament problem. Practice and Theory of Automated Timetabling VI, pages 135-146, 2007. Google Scholar
  9. Marc Goerigk, Richard Hoshino, Ken Kawarabayashi, and Stephan Westphal. Solving the traveling tournament problem by packing three-vertex paths. In Twenty-Eighth AAAI Conference on Artificial Intelligence, pages 2271-2277, 2014. Google Scholar
  10. Richard Hoshino and Ken Kawarabayashi. The linear distance traveling tournament problem. In Twenty-Sixth AAAI Conference on Artificial Intelligence, pages 1770-1778, 2012. Google Scholar
  11. Richard Hoshino and Ken-ichi Kawarabayashi. An approximation algorithm for the bipartite traveling tournament problem. Mathematics of Operations Research, 38(4):720-728, 2013. Google Scholar
  12. Shinji Imahori, Tomomi Matsui, and Ryuhei Miyashiro. A 2.75-approximation algorithm for the unconstrained traveling tournament problem. Annals of Operations Research, 218(1):237-247, 2014. Google Scholar
  13. Graham Kendall, Sigrid Knust, Celso C Ribeiro, and Sebastián Urrutia. Scheduling in sports: An annotated bibliography. Computers &Operations Research, 37(1):1-19, 2010. Google Scholar
  14. Andrew Lim, Brian Rodrigues, and X Zhang. A simulated annealing and hill-climbing algorithm for the traveling tournament problem. European Journal of Operational Research, 174(3):1459-1478, 2006. Google Scholar
  15. Ryuhei Miyashiro, Tomomi Matsui, and Shinji Imahori. An approximation algorithm for the traveling tournament problem. Annals of Operations Research, 194(1):317-324, 2012. Google Scholar
  16. Rasmus V Rasmussen and Michael A Trick. Round robin scheduling-a survey. European Journal of Operational Research, 188(3):617-636, 2008. Google Scholar
  17. Clemens Thielen and Stephan Westphal. Complexity of the traveling tournament problem. Theoretical Computer Science, 412(4):345-351, 2011. Google Scholar
  18. Clemens Thielen and Stephan Westphal. Approximation algorithms for TTP(2). Mathematical Methods of Operations Research, 76(1):1-20, 2012. Google Scholar
  19. Michael Trick. Challenge traveling tournament instances. Online reference at http://mat. gsia. cmu. edu/TOURN/, 2013. Google Scholar
  20. Pascal Van Hentenryck and Yannis Vergados. Population-based simulated annealing for traveling tournaments. In Twenty-Second AAAI Conference on Artificial Intelligence, pages 267-272, 2007. Google Scholar
  21. Stephan Westphal and Karl Noparlik. A 5.875-approximation for the traveling tournament problem. Annals of Operations Research, 218(1):347-360, 2014. Google Scholar
  22. Daisuke Yamaguchi, Shinji Imahori, Ryuhei Miyashiro, and Tomomi Matsui. An improved approximation algorithm for the traveling tournament problem. Algorithmica, 61(4):1077-1091, 2011. Google Scholar
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 About DROPS Imprint Privacy Contact