Ziv Bar-Yossef, Ravi Kumar, et al.
SODA 2002
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 (2002). A quantitatively stronger version of the conjecture implies an inapproximability factor of Ω(√log log n). © Birkhäuser Verlag, Basel 2006.
Related
Andrei Broder, Ravi Kumar, et al.
Computer Networks
Conference paper
Algorithms on negatively curved spaces
Robert Krauthgamer, Jmes R. Lee
FOCS 2006
Ravi Kumar, Prabhakar Raghavan, et al.
ACM TOIT