Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation
Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation
复制标题
限制最大最小公平分配的拟多项式局部搜索
DOI：
10.1145/2818695
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
O. Svensson
中科院分区：
文献类型：
--
作者：
Lukas Polacek;O. Svensson
受限最大-最小公平分配问题(也称为受限圣诞老人问题)是少数几个具有比近似算法更好的估计算法的问题之一。的确，Asadour等人。[2012]证明了对于任意ε>；0，可以使用某一构型Lp在1/(4+ε)的因子范围内估计最优值，但同时不知道如何有效地找到具有可比性能保证的解。从他们的工作中产生的一个自然问题是，这些保证之间的差异是固有的还是由于缺乏适当的技术而产生的。我们通过给出一个具有上述性能保证的拟多项式逼近算法来解决这个问题。更具体地说，我们修改了Asadour等人的本地搜索。[2012]并提供了一种新的分析，使我们可以显著提高其运行时间的界限：从2O(N)到NO(Logn)。我们的技术还具有一个有趣的特性，即尽管我们在分析中使用了相当复杂的配置LP，但我们从未实际解决它，因此得到的算法是纯粹的组合算法。
The restricted max-min fair allocation problem (also known as the restricted Santa Claus problem) is one of few problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, Asadpour et al. [2012] proved that a certain configuration LP can be used to estimate the optimal value within a factor of 1/(4 + ε), for any ε > 0, but at the same time it is not known how to efficiently find a solution with a comparable performance guarantee. A natural question that arises from their work is if the difference between these guarantees is inherent or results from a lack of suitable techniques. We address this problem by giving a quasi-polynomial approximation algorithm with the mentioned performance guarantee. More specifically, we modify the local search of Asadpour et al. [2012] and provide a novel analysis that lets us significantly improve the bound on its running time: from 2O(n) to nO(log n). Our techniques also have the interesting property that although we use the rather complex configuration LP in the analysis, we never actually solve it and therefore the resulting algorithm is purely combinatorial.