Nikhil Bansal, Uriel Feige, et al.
SIAM Journal on Computing
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
Ziv Bar-Yossef, Ravi Kumar, et al.
SODA 2002
Conference paper
Variable Latent Semantic Indexing
Anirban Dasgupta, Prabhakar Raghavan, et al.
KDD 2005
Tuğkan Batu, Eldar Fischer, et al.
Annual Symposium on Foundations of Computer Science - Proceedings