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

Rajsekar Manokaran, Joseph Naor, Prasad Raghavendra, Roy Schwartz

Browse the full STOC paper archive.