Tuğkan Batu, Eldar Fischer, et al.
Annual Symposium on Foundations of Computer Science - Proceedings
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 bursty evolution of blogspace
Ravi Kumar, Jasmine Novak, et al.
WWW 2003
Uriel Feige, Robert Krauthgamer
SIAM Review
Conference paper
Cut-equivalent trees are optimal for min-cut queries
Amir Abboud, Robert Krauthgamer, et al.
FOCS 2020