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