Header menu link for other important links
SDP gaps and UGC hardness for multiway cut, O-extension, and metric labeling
, J. Naor, P. Raghavendra, R. Schwartz
Published in
Pages: 11 - 20
The connection between integrality gaps and computational hardness of discrete optimization problems is an intriguing question. In recent years, this connection has prominently figured in several tight UGG-based hardness results. We show in this paper a direct way of turning integrality gaps into hardness results for several fundamental classification problems. Specifically, we convert linear programming integrality gaps for the Multiway Cut, O-Extension and Metric Labeling problems into UGC-based hardness results. Qualitatively, our result suggests that if the unique games conjecture is true then a linear relaxation of the latter problems studied in several papers (so-called earthrnover linear program) yields the best possible approximation. Taking this a step further, we also obtain integrality gaps for a semi-definite programming relaxation matching the integrality gaps of the earthrnover linear program. Prior to this work, there was an intriguing possibility of obtaining better approximation factors for labeling problems via semi-definite programming. Copyright 2008 ACM.
About the journal
JournalProceedings of the Annual ACM Symposium on Theory of Computing