DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.112

Towards Tight Robust Coresets for k-Medians Clustering

Authors: Lingxiao Huang, Zhenyu Jiang, Yi Li, and Xuan Wu

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

This paper considers coresets for the robust k-medians problem with m outliers, and new constructions in various metric spaces are obtained. Specifically, for metric spaces with a bounded VC or doubling dimension d, the coreset size is O(m) + Õ(kdε^{-2}), which is optimal up to logarithmic factors. For Euclidean spaces, the coreset size is O(mε^{-1}) + Õ(min{k^{4/3}ε^{-2}, kε^{-3}}), improving upon a recent result by Jiang and Lou (ICALP 2025). These results also extend to robust (k,z)-clustering, yielding, for VC and doubling dimension, a coreset size of O(m) + Õ(kdε^{-2z}) with the optimal linear dependence on m. This extended result improves upon the earlier work of Huang et al. (SODA 2025). The techniques introduce novel dataset decompositions, enabling chaining arguments to be applied jointly across multiple components.

Cite as

Lingxiao Huang, Zhenyu Jiang, Yi Li, and Xuan Wu. Towards Tight Robust Coresets for k-Medians Clustering. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 112:1-112:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.ICALP.2026.112,
  author =	{Huang, Lingxiao and Jiang, Zhenyu and Li, Yi and Wu, Xuan},
  title =	{{Towards Tight Robust Coresets for k-Medians Clustering}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{112:1--112:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.112},
  URN =		{urn:nbn:de:0030-drops-265013},
  doi =		{10.4230/LIPIcs.ICALP.2026.112},
  annote =	{Keywords: robust coresets, clustering, k-medians}
}

Search Results

Documents authored by Wu, Xuan

Towards Tight Robust Coresets for k-Medians Clustering

Abstract

Cite as

Thanks for your feedback!

Could not send message