The traveling tournament problem is a well-known benchmark problem of the sports scheduling. We propose an approximation algorithm for the traveling tournament problem with the constraints such that both the number of consecutive home games and that of consecutive away games are at most two (called TTP(2)). The approximation ratio of the proposed algorithm is 1 + 24/n for n teams, which is the first 1 + O(1/n) approximation algorithm for TTP(2).
翻译:巡回锦标赛问题是体育日程安排的一个众所周知的基准问题。 我们为巡回锦标赛问题提出了一个近似算法,其制约因素包括连续在家游戏的数量和连续离场比赛的数量最多为2个(称为TTP(2) ) 。 拟议算法的近似比率是n队1+ 24/n,这是TP(2) 的第一个1+ O(1/n ) 近似算法。