论文标题
通用$ K $ -Median问题的结构迭代舍入舍入
Structural Iterative Rounding for Generalized $k$-Median Problems
论文作者
论文摘要
本文考虑了通用$ K $ - 媒体问题的近似算法。这类问题可以非正式地描述为$ k $ -Median，并具有持续数量的额外约束，其中包括带有异常值的$ K $ -Median和Knapsack中位数。我们的第一个贡献是通用$ k $ -Median的伪ximation算法，该算法输出了$ 6.387 $ -Approximate的解决方案，并具有恒定数量的分数变量。该算法建立在克里希纳斯瓦米（Krishnaswamy），李和桑迪普（Sandeep）的迭代式圆形框架上，以$ k $ -Median的异常值。主要的技术创新是允许在迭代舍入的更丰富的约束集，并利用由此产生的极端点的结构。 使用我们的伪透明算法，我们为$ k $ -Median提供了改进的近似算法，带有异常值和背包中位数。这涉及将我们的伪ximimation与预处理和后处理的步骤相结合，以将恒定数量的分数变量以少量的成本增加。我们的算法达到了近似值$ 6.994 +ε$和$ 6.387 +ε$，分别为$ k $ -Median，分别带有异常值和背包中位数。这些问题上最著名的近似值$ 7.081 +ε$都改善了这两个问题\ cite {dblp：conf/stoc/stoc/stoc/krishnaswamyls18}。
This paper considers approximation algorithms for generalized $k$-median problems. This class of problems can be informally described as $k$-median with a constant number of extra constraints, and includes $k$-median with outliers, and knapsack median. Our first contribution is a pseudo-approximation algorithm for generalized $k$-median that outputs a $6.387$-approximate solution, with a constant number of fractional variables. The algorithm builds on the iterative rounding framework introduced by Krishnaswamy, Li, and Sandeep for $k$-median with outliers. The main technical innovation is allowing richer constraint sets in the iterative rounding and taking advantage of the structure of the resulting extreme points. Using our pseudo-approximation algorithm, we give improved approximation algorithms for $k$-median with outliers and knapsack median. This involves combining our pseudo-approximation with pre- and post-processing steps to round a constant number of fractional variables at a small increase in cost. Our algorithms achieve approximation ratios $6.994 + ε$ and $6.387 + ε$ for $k$-median with outliers and knapsack median, respectively. These improve on the best-known approximation ratio $7.081 + ε$ for both problems \cite{DBLP:conf/stoc/KrishnaswamyLS18}.
