# Structural Iterative Rounding for Generalized k-Median Problems

arXiv: https://arxiv.org/abs/2009.00808 · HTML: https://mlsanity.com/paper/2009.00808/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Sep 2020.

## Built on by (most cited first, 4 of 4)

- [Improved Approximation Algorithms for Individually Fair Clustering](https://mlsanity.com/paper/2106.14043/) (2021)
- [Constant-Factor Approximation Algorithms for Socially Fair k-Clustering](https://mlsanity.com/paper/2206.11210/) (2022)
- [Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means](https://mlsanity.com/paper/2604.16061/) (2026)
- [Simple KNN-Based Outlier Detection Achieves Robust Clustering](https://mlsanity.com/paper/2605.07130/) (2026)

## Abstract (arXiv)

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 citeDBLP:conf/stoc/KrishnaswamyLS18.