Conference paper
Algorithms for ℓp low-rank approximation
Flavio Chierichetti, Sreenivas Gollapudi, et al.
ICML 2017
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
Tuǧkan Batu, Sanjoy Dasgupta, et al.
Proceedings of the Annual IEEE Conference on Computational Complexity
Conference paper
Private approximation of NP-hard functions
Shai Halevi, Robert Krauthgamer, et al.
STOC 2001
Ravi Kumar, Jasmine Novak, et al.
Communications of the ACM