论文标题
社交高尔夫球手和Oberwolfach问题的贪婪算法
A Greedy Algorithm for the Social Golfer and the Oberwolfach Problem
论文作者
论文摘要
受到瑞士系统锦标赛在体育比赛中日益普及的启发，我们研究了预定瑞士系统锦标赛可以保证的回合数量的问题。这些比赛的匹配通常以近视的基于近视的方式确定，取决于以前的回合的结果。加上在比赛期间没有两名球员会遇到一次以上的硬性约束，在某个时候，安排下一轮可能是不可行的。对于具有$ n $播放器的比赛和比赛尺寸为$ k \ geq2 $玩家的比赛，我们证明我们始终可以保证$ \ lfloor \ frac {n} {k（k-1）} \ rfloor $ rounds。我们证明了这一界限很紧。这为社会高尔夫球手问题提供了简单的多项式时间常数因子近似算法。 我们将结果扩展到Oberwolfach问题。我们表明，一种简单的贪婪方法可以保证至少$ \ lfloor \ frac {n+4} {6} \ rfloor $ $ rounds for oberwolfach问题。这会产生一个多项式时间$ \ frac {1} {3+ε} $ - 对于Oberwolfach问题的任何固定$ε> 0 $的近似算法。假设El-Zahar的猜想是正确的，我们改善了基本紧密的回合数量的界限。
Inspired by the increasing popularity of Swiss-system tournaments in sports, we study the problem of predetermining the number of rounds that can be guaranteed in a Swiss-system tournament. Matches of these tournaments are usually determined in a myopic round-based way dependent on the results of previous rounds. Together with the hard constraint that no two players meet more than once during the tournament, at some point it might become infeasible to schedule a next round. For tournaments with $n$ players and match sizes of $k\geq2$ players, we prove that we can always guarantee $\lfloor \frac{n}{k(k-1)} \rfloor$ rounds. We show that this bound is tight. This provides a simple polynomial time constant factor approximation algorithm for the social golfer problem. We extend the results to the Oberwolfach problem. We show that a simple greedy approach guarantees at least $\lfloor \frac{n+4}{6} \rfloor$ rounds for the Oberwolfach problem. This yields a polynomial time $\frac{1}{3+ε}$-approximation algorithm for any fixed $ε>0$ for the Oberwolfach problem. Assuming that El-Zahar's conjecture is true, we improve the bound on the number of rounds to be essentially tight.
