DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2025.28

Coresets for 1-Center in 𝓁₁ Metrics

Authors: Amir Carmel, Chengzhi Guo, Shaofeng H.-C. Jiang, and Robert Krauthgamer

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract

We explore the applicability of coresets - a small subset of the input dataset that approximates a predefined set of queries - to the 1-center problem in 𝓁₁ spaces. This approach could potentially extend to solving the 1-center problem in related metric spaces, and has implications for streaming and dynamic algorithms. We show that in 𝓁₁, unlike in Euclidean space, even weak coresets exhibit exponential dependency on the underlying dimension. Moreover, while inputs with a unique optimal center admit better bounds, they are not dimension independent. We then relax the guarantee of the coreset further, to merely approximate the value (optimal cost of 1-center), and obtain a dimension-independent coreset for every desired accuracy ε > 0. Finally, we discuss the broader implications of our findings to related metric spaces, and show explicit implications to Jaccard and Kendall’s tau distances.

Cite as

Amir Carmel, Chengzhi Guo, Shaofeng H.-C. Jiang, and Robert Krauthgamer. Coresets for 1-Center in 𝓁₁ Metrics. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{carmel_et_al:LIPIcs.ITCS.2025.28,
  author =	{Carmel, Amir and Guo, Chengzhi and Jiang, Shaofeng H.-C. and Krauthgamer, Robert},
  title =	{{Coresets for 1-Center in 𝓁₁ Metrics}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{28:1--28:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.28},
  URN =		{urn:nbn:de:0030-drops-226566},
  doi =		{10.4230/LIPIcs.ITCS.2025.28},
  annote =	{Keywords: clustering, k-center, minimum enclosing balls, coresets, 𝓁₁ norm, Kendall’s tau, Jaccard metric}
}

Search Results

Documents authored by Guo, Chengzhi

Coresets for 1-Center in 𝓁₁ Metrics

Abstract

Cite as

Thanks for your feedback!

Could not send message