Ziv Bar-Yossef, T.S. Jayram, et al.
Journal of Computer and System Sciences
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.
Ziv Bar-Yossef, T.S. Jayram, et al.
Journal of Computer and System Sciences
Ronald Fagin, Ravi Kumar, et al.
SIAM Journal on Discrete Mathematics
Ravi Kumar, Jasmine Novak, et al.
World Wide Web
Ronald Fagin, Ravi Kumar, et al.
SIAM Journal on Discrete Mathematics