Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut.

Shuchi Chawla Anupam Gupta Harald Räcke

Published in: SODA (2005)

Keyphrases

integrality gap
positive and negative
dimensionality reduction
linear program
closed form
error bounds
low dimensional
vector space
approximation error
multiscale
high dimensional data
manifold learning
euclidean space
relative error
set valued