论文标题
TTP保证近似值的实用算法，最大巡回赛长度两个
Practical Algorithms with Guaranteed Approximation Ratio for TTP with Maximum Tour Length Two
论文作者
论文摘要
旅行锦标赛问题（TTP）是一个受到美国职棒大联盟启发的艰难但有趣的体育安排问题，即设计双圆形旋转式计划，以便每支球队在彼此的家庭场地中玩一场比赛，最大程度地减少所有$ N $团队的总距离（$ n $偶数）。在本文中，我们认为TTP-2，即TTP受到限制，即每支球队连续两次主场比赛或客场比赛。我们提出了具有提高近似比的TTP-2的实用算法。由于该问题的结构属性不同，因此所有已知的TTP-2算法都不同，$ n/2 $是奇怪的，甚至是奇数，并且对于这两种情况，我们的算法也有所不同。对于$ n/2 $，我们的近似值为$ 1+3/n $，提高了先前的$ 1+4/n $的结果。对于奇数$ n/2 $，我们的近似值为$ 1+5/n $，改善了$ 3/2+6/n $的先前结果。实际上，我们的算法易于实现。著名基准集的实验表明，我们的算法在所有情况下都击败了以前已知的解决方案，平均提高了5.66美元\％$。
The Traveling Tournament Problem (TTP) is a hard but interesting sports scheduling problem inspired by Major League Baseball, which is to design a double round-robin schedule such that each pair of teams plays one game in each other's home venue, minimizing the total distance traveled by all $n$ teams ($n$ is even). In this paper, we consider TTP-2, i.e., TTP under the constraint that at most two consecutive home games or away games are allowed for each team. We propose practical algorithms for TTP-2 with improved approximation ratios. Due to the different structural properties of the problem, all known algorithms for TTP-2 are different for $n/2$ being odd and even, and our algorithms are also different for these two cases. For even $n/2$, our approximation ratio is $1+3/n$, improving the previous result of $1+4/n$. For odd $n/2$, our approximation ratio is $1+5/n$, improving the previous result of $3/2+6/n$. In practice, our algorithms are easy to implement. Experiments on well-known benchmark sets show that our algorithms beat previously known solutions for all instances with an average improvement of $5.66\%$.
