论文标题
改进的双点四舍五入算法和$ k $ -Median的金屏障
Improved Bi-point Rounding Algorithms and a Golden Barrier for $k$-Median
论文作者
论文摘要
$ K $ -Median的当前最佳近似算法依赖于首先获得称为双点溶液的结构化分数解决方案，然后将其四舍五入到整数溶液中。我们通过统一和完善先前的方法来改善第二步。我们描述了设施日益复杂的分区方案的层次结构，以及相应的一组算法和依赖因子的非线性程序。我们证明，该层次结构的第三层是$ 2.613 $ - APPROXIMATION，以$ 2.675 $的最佳比率提高，而在拟议的分析下，没有任何一层比$ 2.588 $更好。 在负面的一面，我们给出了一系列双点解决方案，即使允许打开$ k+o（k）$设施，这些解决方案也不能比黄金比的平方根更好。这给出了当前方法的障碍，该方法获得了比$ 2 \ sqrtϕ \约2.544 $更好的近似值。我们总共将双点溶液的近似差距减少了三分之二。
The current best approximation algorithms for $k$-median rely on first obtaining a structured fractional solution known as a bi-point solution, and then rounding it to an integer solution. We improve this second step by unifying and refining previous approaches. We describe a hierarchy of increasingly-complex partitioning schemes for the facilities, along with corresponding sets of algorithms and factor-revealing non-linear programs. We prove that the third layer of this hierarchy is a $2.613$-approximation, improving upon the current best ratio of $2.675$, while no layer can be proved better than $2.588$ under the proposed analysis. On the negative side, we give a family of bi-point solutions which cannot be approximated better than the square root of the golden ratio, even if allowed to open $k+o(k)$ facilities. This gives a barrier to current approaches for obtaining an approximation better than $2 \sqrtϕ \approx 2.544$. Altogether we reduce the approximation gap of bi-point solutions by two thirds.
