# An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2014.

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

- [Better Algorithms for Individually Fair k-Clustering](https://mlsanity.com/paper/2106.12150/) (2021)
- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [Fair Clustering Under a Bounded Cost](https://mlsanity.com/paper/2106.07239/) (2021)
- [Replicable Clustering](https://mlsanity.com/paper/2302.10359/) (2023)
- [Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints](https://mlsanity.com/paper/2103.02013/) (2021)
- [Nearly-Tight and Oblivious Algorithms for Explainable Clustering](https://mlsanity.com/paper/2106.16147/) (2021)
- [Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets](https://mlsanity.com/paper/2204.04828/) (2022)
- [Near-optimal Algorithms for Explainable k-Medians and k-Means](https://mlsanity.com/paper/2107.00798/) (2021)
- [Almost Tight Approximation Algorithms for Explainable Clustering](https://mlsanity.com/paper/2107.00774/) (2021)
- [Scalable Differentially Private Clustering via Hierarchically Separated Trees](https://mlsanity.com/paper/2206.08646/) (2022)
- [Optimistic No-regret Algorithms for Discrete Caching](https://mlsanity.com/paper/2208.06414/) (2022)
- [Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics](https://mlsanity.com/paper/2111.10912/) (2021)
- [Interpretable Clustering: A Survey](https://mlsanity.com/paper/2409.00743/) (2024)
- [Efficient Algorithms For Fair Clustering with a New Fairness Notion](https://mlsanity.com/paper/2109.00708/) (2021)
- [k-Median Clustering via Metric Embedding: Towards Better Initialization with Differential Privacy](https://mlsanity.com/paper/2206.12895/) (2022)
- [Diversity-aware clustering: Computational Complexity and Approximation Algorithms](https://mlsanity.com/paper/2401.05502/) (2024)
- [Coresets for constrained k-median and k-means clustering in low dimensional Euclidean space](https://mlsanity.com/paper/2106.07319/) (2021)
- [Ascent Similarity Caching with Approximate Indexes](https://mlsanity.com/paper/2107.00957/) (2021)
- [Simple, Scalable and Effective Clustering via One-Dimensional Projections](https://mlsanity.com/paper/2310.16752/) (2023)
- [The Fairness-Quality Trade-off in Clustering](https://mlsanity.com/paper/2408.10002/) (2024)
- [Clustering to Minimize Cluster-Aware Norm Objectives](https://mlsanity.com/paper/2410.24104/) (2024)
- [Can Evolutionary Clustering Have Theoretical Guarantees?](https://mlsanity.com/paper/2212.01771/) (2022)
- [A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering](https://mlsanity.com/paper/2405.10378/) (2024)
- [A Broader View on Clustering under Cluster-Aware Norm Objectives](https://mlsanity.com/paper/2512.06211/) (2025)
- [Clustering with Label Consistency](https://mlsanity.com/paper/2512.19654/) (2025)
- [Hierarchical F-Clustering: Approximation and Hardness of Clustering into Trees and Bounded Diameter Graphs](https://mlsanity.com/paper/2607.13217/) (2026)

## Abstract (arXiv)

Dependent rounding is a useful technique for optimization problems with hard budget constraints. This framework naturally leads to negative correlation properties. However, what if an application naturally calls for dependent rounding on the one hand, and desires positive correlation on the other? More generally, we develop algorithms that guarantee the known properties of dependent rounding, but also have nearly best-possible behavior - near-independence, which generalizes positive correlation - on "small" subsets of the variables. The recent breakthrough of Li & Svensson for the classical k-median problem has to handle positive correlation in certain dependent-rounding settings, and does so implicitly. We improve upon Li-Svensson's approximation ratio for k-median from 2.732 + ε to 2.675 + ε by developing an algorithm that improves upon various aspects of their work. Our dependent-rounding approach helps us improve the dependence of the runtime on the parameter ε from Li-Svensson's NO(1/ε2) to NO((1/ε) log(1/ε)).