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 <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10479_2025_6483_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">$k\ge 4$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≥</mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10479_2025_6483_Article_IEq2.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="43" /> </InlineMediaObject> <EquationSource Format="TEX">$n\ge 6$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>6</mn> </mrow> </math></EquationSource> </InlineEquation>. 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 <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10479_2025_6483_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="60" /> </InlineMediaObject> <EquationSource Format="TEX">$k \ge n/2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≥</mo> <mi>n</mi> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, the approximation ratio can be improved to 4.

A 5-approximation algorithm for the traveling tournament problem

期刊论文
发表日期：

2025年1月21日

查看全文

Jingyang Zhao,
Mingyu Xiao

摘要

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\ge 4$ $k \geq 4$ and $n\ge 6$ $n \geq 6$ . 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 \ge n/2$ $k \geq n / 2$ , the approximation ratio can be improved to 4.