28 citations · 70 across the 20 of their papers we have counts for
Showing 2011Show all
2 papers · 1 filter
cs.CC2011★ 28 cited
The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme
Yair Bartal, Lee-Ad Gottlieb, Robert Krauthgamer
The Traveling Salesman Problem (TSP) is among the most famous NP-hard optimization problems. We design for this problem a randomized polynomial-time algorithm that computes a (1+ep…
cs.LG2011
Efficient Regression in Metric Spaces via Approximate Lipschitz Extension
Lee-Ad Gottlieb, Aryeh Kontorovich, Robert Krauthgamer
We present a framework for performing efficient regression in general metric spaces. Roughly speaking, our regressor predicts the value at a new point by computing a Lipschitz exte…