论文标题
圣诞老人的更好的树木
Better Trees for Santa Claus
论文作者
论文摘要
我们重新审视了Bateni等人引入的Max-Min Gunborescence的问题。 [stoc'09]作为圣诞老人普通问题的中心特殊情况，它构成了近似算法中臭名昭著的开放问题。在前一种问题中，我们给了一个有向源和水槽的有向图，我们的目标是找到植根于来源的顶点脱节的arborescences，以便在树状的每个非链接顶点上，超高度至少为$ k $，其中$ k $是最大化的。 这个问题特别令人感兴趣，因为它似乎捕获了圣诞老人问题的许多困难：（1）与圣诞老人问题中的配置LP在这种情况下具有较大的完整性差距，并且（2）Bateni等人先前的进展。很快被概括为圣诞老人问题（Chakrabarty等人[focs'09]）。这些结果既是圣诞老人问题和最高敏感性树脂的最新结果，并且在准多物种时间中产生了聚类的近似值。我们对此提出了指数的改进，即最大值 - 最高度表现问题的准级 - 多态时间的$ \ mathrm {poly}（\ log \ log n）$ - 近似。据我们所知，这是为圣诞老人问题的特殊情况打破对数障碍的第一个示例，在这种情况下，配置LP无法使用。
We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC'09] as a central special case of the general Santa Claus problem, which constitutes a notorious open question in approximation algorithms. In the former problem we are given a directed graph with sources and sinks and our goal is to find vertex disjoint arborescences rooted in the sources such that at each non-sink vertex of an arborescence the out-degree is at least $k$, where $k$ is to be maximized. This problem is of particular interest, since it appears to capture much of the difficulty of the Santa Claus problem: (1) like in the Santa Claus problem the configuration LP has a large integrality gap in this case and (2) previous progress by Bateni et al. was quickly generalized to the Santa Claus problem (Chakrabarty et al. [FOCS'09]). These results remain the state-of-the-art both for the Santa Claus problem and for max-min degree arborescence and they yield a polylogarithmic approximation in quasi-polynomial time. We present an exponential improvement to this, a $\mathrm{poly}(\log\log n)$-approximation in quasi-polynomial time for the max-min degree arborescence problem. To the best of our knowledge, this is the first example of breaking the logarithmic barrier for a special case of the Santa Claus problem, where the configuration LP cannot be utilized.
