论文标题
通过迭代舍入的耐断层中值问题的恒定近似
Constant approximation for fault-tolerant median problems via iterative rounding
论文作者
论文摘要
在本文中，我们研究了耐断层的基质中位数和容忍性背包中位数问题。这两个问题概括了许多基本的聚类和设施的位置问题，例如统一的耐故障$ k $ - 米德式，易于故障的设施位置，矩形中位数，knapsack中位数等。我们提供了一个多功能的迭代式圆形圆形框架，并获得一个统一的恒定物质近似近似算法。
In this paper, we study the fault-tolerant matroid median and fault-tolerant knapsack median problems. These two problems generalize many fundamental clustering and facility location problems, such as uniform fault-tolerant $k$-median, uniform fault-tolerant facility location, matroid median, knapsack median, etc. We present a versatile iterative rounding framework and obtain a unifying constant-factor approximation algorithm.
