Ravi Kumar, Jasmine Novak, et al.
Communications of the ACM
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
Conference paper
On the hardness of approximating multicut and sparsest-cut
Shuchi Chawla, Robert Krauthgamer, et al.
CCC 2005
Conference paper
Two applications of information complexity
T.S. Jayram, Ravi Kumar, et al.
STOC 2003
Conference paper
Discovering large dense subgraphs in massive graphs
David Gibson, Ravi Kumar, et al.
VLDB 2005