$k$-Clustering via Iterative Randomized Rounding
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917388494045184 |
|---|---|
| author | Byrka, Jarosław Guo, Yuhao Hu, Yang Li, Shi Wan, Chengzhang Wang, Zaixuan |
| author_facet | Byrka, Jarosław Guo, Yuhao Hu, Yang Li, Shi Wan, Chengzhang Wang, Zaixuan |
| contents | In this work we propose a single rounding algorithm for the fractional solutions of the standard LP relaxation for $k$-clustering. As a starting point, we obtain an iterative rounding $(\frac{3^p + 1}{2})$-Lagrangian Multiplier-Perserving (LMP) approximation for the $k$-clustering problem with the cost function being the $p$-th power of the distance. Such an algorithm outputs a random solution that opens $k$ facilities \emph{in expectation}, whose cost in expectation is at most $\frac{3^p + 1}{2}$ times the optimum cost. Thus, we recover the $2$-LMP approximation for $k$-median by Jain et al.~[JACM'03], which played a central role in deriving the current best $2$ approximation for $k$-median. Unlike the result of Jain et al., our algorithm is based on LP rounding, and it can be easily adapted to the $L_p^p$-cost setting. For the Euclidean $k$-means problem, the LMP factor we obtain is $\frac{11}{3}$, which is better than the $5$ approximation given by this framework for general metrics.
Then, we show how to convert the LMP-approximation algorithms to a true-approximation, with only a $(1+\varepsilon)$ factor loss in the approximation ratio. We obtain a ($\frac{3^p + 1}{2}+\varepsilon$)-approximation algorithm for $k$-clustering with cost function being the $p$-th power of the distance, for $p \geq 1$. This reproduces the best known ($2+\varepsilon$)-approximation for $k$-median by Cohen-Addad et al. [STOC'25], and improves the approximation factor for metric $k$-means from 5.83 by Charikar at al. [FOCS'25] to $5+\varepsilon$ in our framework. Moreover, the same algorithm, but with a specialized analysis, attains ($4+\varepsilon$)-approximation for Euclidean $k$-means matching the recent result by Charikar et al. [STOC'26]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_06046 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | $k$-Clustering via Iterative Randomized Rounding Byrka, Jarosław Guo, Yuhao Hu, Yang Li, Shi Wan, Chengzhang Wang, Zaixuan Data Structures and Algorithms In this work we propose a single rounding algorithm for the fractional solutions of the standard LP relaxation for $k$-clustering. As a starting point, we obtain an iterative rounding $(\frac{3^p + 1}{2})$-Lagrangian Multiplier-Perserving (LMP) approximation for the $k$-clustering problem with the cost function being the $p$-th power of the distance. Such an algorithm outputs a random solution that opens $k$ facilities \emph{in expectation}, whose cost in expectation is at most $\frac{3^p + 1}{2}$ times the optimum cost. Thus, we recover the $2$-LMP approximation for $k$-median by Jain et al.~[JACM'03], which played a central role in deriving the current best $2$ approximation for $k$-median. Unlike the result of Jain et al., our algorithm is based on LP rounding, and it can be easily adapted to the $L_p^p$-cost setting. For the Euclidean $k$-means problem, the LMP factor we obtain is $\frac{11}{3}$, which is better than the $5$ approximation given by this framework for general metrics. Then, we show how to convert the LMP-approximation algorithms to a true-approximation, with only a $(1+\varepsilon)$ factor loss in the approximation ratio. We obtain a ($\frac{3^p + 1}{2}+\varepsilon$)-approximation algorithm for $k$-clustering with cost function being the $p$-th power of the distance, for $p \geq 1$. This reproduces the best known ($2+\varepsilon$)-approximation for $k$-median by Cohen-Addad et al. [STOC'25], and improves the approximation factor for metric $k$-means from 5.83 by Charikar at al. [FOCS'25] to $5+\varepsilon$ in our framework. Moreover, the same algorithm, but with a specialized analysis, attains ($4+\varepsilon$)-approximation for Euclidean $k$-means matching the recent result by Charikar et al. [STOC'26]. |
| title | $k$-Clustering via Iterative Randomized Rounding |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2604.06046 |