The Traveling Tournament Problem with Maximum Tour Length Two: A Practical Algorithm with an Improved Approximation Bound
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.
Cite
Text
Zhao and Xiao. "The Traveling Tournament Problem with Maximum Tour Length Two: A Practical Algorithm with an Improved Approximation Bound." International Joint Conference on Artificial Intelligence, 2021. doi:10.24963/IJCAI.2021/578Markdown
[Zhao and Xiao. "The Traveling Tournament Problem with Maximum Tour Length Two: A Practical Algorithm with an Improved Approximation Bound." International Joint Conference on Artificial Intelligence, 2021.](https://mlanthology.org/ijcai/2021/zhao2021ijcai-traveling/) doi:10.24963/IJCAI.2021/578BibTeX
@inproceedings{zhao2021ijcai-traveling,
title = {{The Traveling Tournament Problem with Maximum Tour Length Two: A Practical Algorithm with an Improved Approximation Bound}},
author = {Zhao, Jingyang and Xiao, Mingyu},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2021},
pages = {4206-4212},
doi = {10.24963/IJCAI.2021/578},
url = {https://mlanthology.org/ijcai/2021/zhao2021ijcai-traveling/}
}