Search Results

Documents authored by Petruschka, Nir

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.30
Optimal Stable Coresets for Geometric Median via Uniform Sampling

Authors: Amir Carmel, Robert Krauthgamer, and Nir Petruschka

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract
The geometric median problem asks to find a point in ℝ^d that minimizes the sum of Euclidean distances to an input set. It is a classical problem in computational geometry and appears as a subroutine in numerous optimization tasks, many of which require the solution to satisfy additional structural constraints. A common approach to reduce the input size is to construct a coreset, which is a small weighted subset that faithfully represents the input for a specific optimization problem. Strong coresets preserve the cost of every candidate solution but require linear time to construct; weak coresets admit sublinear construction, in fact by uniform sampling, but only preserve near-optimal solutions, which is insufficient when the solution is constrained. To address this, we focus instead on the recently introduced intermediate notion of a stable coreset, which simultaneously handles all constrained variants. Currently, there is a large gap between the known sample sizes for stable and weak coresets. Our main result is that a uniform sample of size O(ε^{-2} log 1/ε) is a stable (ε, O(ε))-coreset for the geometric median, with high constant probability, and this bound is tight up to the logarithmic factor. Our analysis adapts recent machinery of Carmel and Krauthgamer (ICLR 2026) for constructing stable coresets, which incurs an O(log d) factor. We show an iterative argument that progressively reduces the sample size, and eliminates this dependence on the dimension d. At a high level, this approach resembles the technique of iterative size reduction, which is applicable for strong coresets but not for weak coresets.
Cite as

Amir Carmel, Robert Krauthgamer, and Nir Petruschka. Optimal Stable Coresets for Geometric Median via Uniform Sampling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{carmel_et_al:LIPIcs.APPROX/RANDOM.2026.30,
  author =	{Carmel, Amir and Krauthgamer, Robert and Petruschka, Nir},
  title =	{{Optimal Stable Coresets for Geometric Median via Uniform Sampling}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{30:1--30:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.30},
  URN =		{urn:nbn:de:0030-drops-277475},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.30},
  annote =	{Keywords: clustering, geometric median, coresets, stable coresets, uniform sampling}
}
Document
DOI: 10.4230/LIPIcs.ESA.2026.95
Fast Metric Decompositions in High Dimension

Authors: Robert Krauthgamer, Asaf Petruschka, and Nir Petruschka

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
Metric decompositions are a fundamental tool in the design of algorithms involving distances. We study fast algorithms for sampling from probabilistic metric decompositions of n-point sets in 𝓁_∞ and 𝓁₂ spaces of high dimension d. For 𝓁_∞, we design a padded-decomposition algorithm that runs in time Õ(nd²), which is near-linear in n, and achieves padding parameter Õ(log n). Our algorithm constructs a new sparse neighborhood cover that is based on geometric properties of 𝓁_∞ [Indyk, JCSS'01], and utilizes recent reductions between covers and decompositions [Conroy and Filtser, STOC'25]. For 𝓁₂, we design a separating-decomposition algorithm that achieves near optimal separation Õ(√{log n}) in almost-linear time n^{1+o(1)}. Our bounds improve over known algorithms with similar running time by a factor Ω(√{log n}), and the techniques have additional applications to spanners and nearest-neighbor search.
Cite as

Robert Krauthgamer, Asaf Petruschka, and Nir Petruschka. Fast Metric Decompositions in High Dimension. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 95:1-95:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{krauthgamer_et_al:LIPIcs.ESA.2026.95,
  author =	{Krauthgamer, Robert and Petruschka, Asaf and Petruschka, Nir},
  title =	{{Fast Metric Decompositions in High Dimension}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{95:1--95:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.95},
  URN =		{urn:nbn:de:0030-drops-272315},
  doi =		{10.4230/LIPIcs.ESA.2026.95},
  annote =	{Keywords: Metric Spaces, Separating Decomposition, Padded Decomposition}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.66
Fast Nearest Neighbor Search for 𝓁_p Metrics

Authors: Robert Krauthgamer and Nir Petruschka

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
The Nearest Neighbor Search (NNS) problem asks to design a data structure that preprocesses an n-point dataset X lying in a metric space ℳ, so that given a query point q ∈ ℳ, one can quickly return a point of X minimizing the distance to q. The efficiency of such a data structure is evaluated primarily by the amount of space it uses and the time required to answer a query. We focus on the fast query-time regime, which is crucial for modern large-scale applications, where datasets are massive and queries must be processed online, and is often modeled by query time poly(d log n) when ℳ is a d-dimensional normed space. Our main result is such a randomized data structure for NNS in 𝓁_p^d spaces, p > 2, that achieves p^{O(1) + log log p} approximation with fast query time and poly(dn) space. Our data structure improves, or is incomparable to, the state-of-the-art for the fast query-time regime from [Bartal and Gottlieb, TCS 2019] and [Krauthgamer, Petruschka and Sapir, FOCS 2025].
Cite as

Robert Krauthgamer and Nir Petruschka. Fast Nearest Neighbor Search for 𝓁_p Metrics. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 66:1-66:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{krauthgamer_et_al:LIPIcs.SoCG.2026.66,
  author =	{Krauthgamer, Robert and Petruschka, Nir},
  title =	{{Fast Nearest Neighbor Search for 𝓁\underlinep Metrics}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{66:1--66:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.66},
  URN =		{urn:nbn:de:0030-drops-258737},
  doi =		{10.4230/LIPIcs.SoCG.2026.66},
  annote =	{Keywords: Nearest neighbor search, metric embeddings, 𝓁\underlinep norm}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.66
Lipschitz Decompositions of Finite 𝓁_{p} Metrics

Authors: Robert Krauthgamer and Nir Petruschka

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Lipschitz decomposition is a useful tool in the design of efficient algorithms involving metric spaces. While many bounds are known for different families of finite metrics, the optimal parameters for n-point subsets of 𝓁_p, for p > 2, remained open, see e.g. [Naor, SODA 2017]. We make significant progress on this question and establish the bound β = O(log^{1-1/p} n). Building on prior work, we demonstrate applications of this result to two problems, high-dimensional geometric spanners and distance labeling schemes. In addition, we sharpen a related decomposition bound for 1 < p < 2, due to Filtser and Neiman [Algorithmica 2022].
Cite as

Robert Krauthgamer and Nir Petruschka. Lipschitz Decompositions of Finite 𝓁_{p} Metrics. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 66:1-66:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{krauthgamer_et_al:LIPIcs.SoCG.2025.66,
  author =	{Krauthgamer, Robert and Petruschka, Nir},
  title =	{{Lipschitz Decompositions of Finite 𝓁\underline\{p\} Metrics}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{66:1--66:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.66},
  URN =		{urn:nbn:de:0030-drops-232182},
  doi =		{10.4230/LIPIcs.SoCG.2025.66},
  annote =	{Keywords: Lipschitz decompositions, metric embeddings, geometric spanners}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact