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 2019Show all

3 papers · 1 filter

cs.LG2019★ 1 cited

Classification in asymmetric spaces via sample compression

Lee-Ad Gottlieb, Shira Ozeri

We initiate the rigorous study of classification in quasi-metric spaces. These are point sets endowed with a distance function that is non-negative and also satisfies the triangle…

cs.DS2019

Labelings vs. Embeddings: On Distributed Representations of Distances

Arnold Filtser, Lee-Ad Gottlieb, Robert Krauthgamer

We investigate for which metric spaces the performance of distance labeling and of $ℓ_{\infty}$ -embeddings differ, and how significant can this difference be. Recall that a distan…

cs.CG2019★ 1 cited

Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces

Lee-Ad Gottlieb, Yair Bartal

We give an algorithm that computes a $(1 + ε)$ -approximate Steiner forest in near-linear time $n \cdot 2^{(1/ ε)^{O (dd i m^{2})} (l o g l o g n)^{2}}$ . This is a dramatic improvement upon the…