Constant Approximation for $k$-Median and $k$-Means with Outliers via Iterative Rounding

Ravishankar Krishnaswamy, Shi Li, Sai Sandeep

In this paper, we present a new iterative rounding framework for many clustering problems. Using this, we obtain an $({\alpha }_1+\epsilon \le 7.081+\epsilon )$-approximation algorithm for $k$-median…