Ziv Bar-Yossef, T.S. Jayram, et al.
Journal of Computer and System Sciences
Conference paper
On the hardness of approximating multicut and sparsest-cut
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.