Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling.

Rajsekar Manokaran Joseph Naor Prasad Raghavendra Roy Schwartz

Published in: STOC (2008)

Keyphrases

metric learning
semidefinite programming
distance measure
user generated content
active learning
distance function
computational complexity
linear programming
euclidean distance
semi definite programming
np complete
unsupervised learning
phase transition
evaluation metrics
tree structures