Publication
CCC 2005
Conference paper

On the hardness of approximating multicut and sparsest-cut

View publication

Abstract

We show that the MULTICUT, SPARSEST-CUT, and MIN-2CNF= DELETION problems are NP-hard to approximate within every constant factor, assuming the Unique Games Conjecture of Khot [STOC, 2002]. A quantitatively stronger version of the conjecture implies inapproximability factor of Ω(log log n). © 2005 IEEE.

Date

Publication

CCC 2005

Authors

Share