Ronald Fagin, Ravi Kumar, et al.
SIGMOD 2003
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
Ravi Kumar, Prabhakar Raghavan, et al.
Computer Networks
Conference paper
Object location in realistic networks
Kirsten Hildrum, Robert Krauthgamer, et al.
SPAA 2004
Conference paper
Cell-probe lower bounds for the partial match problem
T.S. Jayram, Subhash Khot, et al.
STOC 2003