Centrality of Trees for Capacitated k-Center
Centrality of Trees for Capacitated k-Center
复制标题
能力 k 中心树的中心性
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Ola Svensson
中科院分区：
文献类型：
--
作者：
Hyung;Aditya Bhaskara;Ola Svensson
我们对网络位置问题的无能力版本和有能力版本的理解有很大的差异。经典的k-中心问题可能最好地说明了这一点：对于无能力版本，有一个简单的紧2近似算法，而对于有能力的一般版本，第一个恒定因子近似算法是最近才通过使用复杂的舍入算法获得的，该算法实现了数百个近似保证。
我们的论文旨在弥合这一差异。对于有容量约束的k-中心问题，我们给出了一个简单的算法，分析清楚，它允许我们证明近似保证为9。它使用标准的Lp松弛，接近于解决完整性差距(经过必要的预处理)，这个差距被缩小到7，8或9。该算法首先归结为特殊的树实例，然后对这些实例进行最优求解。我们的树实例的概念是非常通用的，并适用于容量受限k-中心问题的自然变体，对于该问题，我们也得到了改进的算法。最后，我们给出的证据表明，对于所有非零容量相同的情况，通过给出一个克服完整性缺口的近似算法，更强大的预处理可以带来更好的算法。
There is a large discrepancy in our understanding of uncapacitated and capacitated versions of network location problems. This is perhaps best illustrated by the classical k-center problem: there is a simple tight 2-approximation algorithm for the uncapacitated version whereas the first constant factor approximation algorithm for the general version with capacities was only recently obtained by using an intricate rounding algorithm that achieves an approximation guarantee in the hundreds.
Our paper aims to bridge this discrepancy. For the capacitated k-center problem, we give a simple algorithm with a clean analysis that allows us to prove an approximation guarantee of 9. It uses the standard LP relaxation and comes close to settling the integrality gap (after necessary preprocessing), which is narrowed down to either 7, 8 or 9. The algorithm proceeds by first reducing to special tree instances, and then solves such instances optimally. Our concept of tree instances is quite versatile, and applies to natural variants of the capacitated k-center problem for which we also obtain improved algorithms. Finally, we give evidence to show that more powerful preprocessing could lead to better algorithms, by giving an approximation algorithm that beats the integrality gap for instances where all non-zero capacities are uniform.