Conference paper
Approximate counting of inversions in a data stream
Miklós Ajtai, T.S. Jayram, et al.
STOC 2002
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.
Miklós Ajtai, T.S. Jayram, et al.
STOC 2002
Ronald Fagin, Ravi Kumar, et al.
WWW 2003
Ravi Kumar, Jasmine Novak, et al.
World Wide Web
Ziv Bar-Yossef, T.S. Jayram, et al.
Journal of Computer and System Sciences