Proceedings

The Traveling Tournament Problem with Maximum Tour Length Two: A Practical Algorithm with An Improved Approximation Bound

Jingyang Zhao, Mingyu Xiao

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 4206-4212.

https://doi.org/10.24963/ijcai.2021/578

Keywords

  • Planning and Scheduling: Planning Algorithms
  • Planning and Scheduling: Theoretical Foundations of Planning
  • Planning and Scheduling: Scheduling

Abstract

The Traveling Tournament Problem is a well-known benchmark problem in tournament timetabling, which asks us to design a schedule of home/away games of n teams (n is even) under some feasibility requirements such that the total traveling distance of all the n teams is minimized. In this paper, we study TTP-2, the traveling tournament problem where at most two consecutive home games or away games are allowed, and give an effective algorithm for n/2 being odd. Experiments on the well-known benchmark sets show that we can beat previously known solutions for all instances with n/2 being odd by an average improvement of 2.66%. Furthermore, we improve the theoretical approximation ratio from 3/2+O(1/n) to 1+O(1/n) for n/2 being odd, answering a challenging open problem in this area.

Jingyang Zhao, and Mingyu Xiao. 2021. The Traveling Tournament Problem with Maximum Tour Length Two: A Practical Algorithm with An Improved Approximation Bound. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 4206–4212. https://doi.org/10.24963/ijcai.2021/578
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards