The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract)
Approximation schemes for Euclidean k-medians and related problems
On approximating arbitrary metrices by tree metrics
Approximating geometrical graphs via “spanners” and “banyans”
A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
Approximate nearest neighbors