.png){kind=icon}
.png){kind=icon}
Return
A 5-approximation algorithm for the traveling tournament problem
.png){kind=icon}
PRE
AI
DOI：10.1007/s10479-025-06483-1.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The Traveling Tournament Problem (TTP-k) is a well-known benchmark problem in tournament timetabling, which asks us to design a double round-robin schedule such that the total traveling distance of all n teams is minimized under the constraints that each pair of teams plays one game in each other's home venue, and each team plays at most k-consecutive home games or away games. Westphal and Noparlik (Ann. Oper. Res. 218(1):347-360, 2014) claimed a 5.875-approximation algorithm for all k >= 4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k\ge 4$$\end{document} and n >= 6\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n\ge 6$$\end{document}. However, there were both flaws in the construction of the schedule and in the analysis. In this paper, we show that there is a 5-approximation algorithm for all k and n. Furthermore, if k >= n/2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \ge n/2$$\end{document}, the approximation ratio can be improved to 4.
Keywords:
Approximation algorithms
Sports scheduling
Traveling tournament problem
Timetabling
Combinatorial optimization
Journal
IF:
4.5
Papers:
8.0K
Citations:
2.1W
Organization
No organization information available