Structural iterative rounding for generalized k-median problems
本文提出一种伪近似算法，通过结构迭代取整框架解决带异常值的k-中位数和背包中位数问题，分别达到6.994+ε和6.387+ε的近似比，优于此前已知的7.081+ε。
Abstract This paper considers approximation algorithms for generalized k -median problems. These 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 as reported (Krishnaswamy et al. in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018). The main technical innovation is allowing richer constraint sets in the iterative rounding and using 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 + \epsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>6.994</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ϵ</mml:mi> </mml:mrow> </mml:math> and $$6.387 + \epsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>6.387</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ϵ</mml:mi> </mml:mrow> </mml:math> for k -median with outliers and knapsack median, respectively. These improve on the best-known approximation ratio $$7.081 + \epsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>7.081</mml:mn> <mml:mo>+</mml:mo> <mml:mi>ϵ</mml:mi> </mml:mrow> </mml:math> for both problems as reported (Krishnaswamy et al. in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018).