Nir Petruschka

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2026

Fast Metric Decompositions in High Dimension

Robert Krauthgamer, Asaf Petruschka, Nir Petruschka

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$ -…

cs.DS2026

Optimal Stable Coresets for Geometric Median via Uniform Sampling

Amir Carmel, Robert Krauthgamer, Nir Petruschka

The geometric median problem asks to find a point in $R^{d}$ that minimizes the sum of Euclidean distances to an input set. It is a classical problem in computational geomet…

cs.DS2026

Fast Nearest Neighbor Search for $ℓ_{p}$ Metrics

Robert Krauthgamer, Nir Petruschka

The Nearest Neighbor Search (NNS) problem asks to design a data structure that preprocesses an $n$ -point dataset $X$ lying in a metric space $M$ , so that given a query po…

Fast Metric Decompositions in High Dimension

Optimal Stable Coresets for Geometric Median via Uniform Sampling

Fast Nearest Neighbor Search for ℓp​ Metrics

Fast Nearest Neighbor Search for $ℓ_{p}$ Metrics