Lee-Ad Gottlieb

activity

20092025

most citedThe Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme

28 citations · 70 across the 20 of their papers we have counts for

collaborators

Showing 2015Show all

3 papers · 1 filter

cs.CG2015★ 2 cited

Approximate nearest neighbor search for $ℓ_{p}$ -spaces ( $2 < p < \infty$ ) via embeddings

Yair Bartal, Lee-Ad Gottlieb

While the problem of approximate nearest neighbor search has been well-studied for Euclidean space and $ℓ_{1}$ , few non-trivial algorithms are known for $ℓ_{p}$ when ($2 < p < \i…

cs.CG2015★ 9 cited

A light metric spanner

Lee-Ad Gottlieb

It has long been known that $d$ -dimensional Euclidean point sets admit $(1 + ε)$ -stretch spanners with lightness $W_{E} = ε^{- O (d)}$ , that is total edge weight at most $W_{E}$ times the…

cs.LG2015★ 3 cited

Nearly optimal classification for semimetrics

Lee-Ad Gottlieb, Aryeh Kontorovich

We initiate the rigorous study of classification in semimetric spaces, which are point sets with a distance function that is non-negative and symmetric, but need not satisfy the tr…

Approximate nearest neighbor search for ℓp​-spaces (2<p<∞) via embeddings

A light metric spanner

Nearly optimal classification for semimetrics

Approximate nearest neighbor search for $ℓ_{p}$ -spaces ( $2 < p < \infty$ ) via embeddings