Conference paper
How hard is it to approximate the best Nash equilibrium?
Elad Hazan, Robert Krauthgamer
SODA 2009
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.
Elad Hazan, Robert Krauthgamer
SODA 2009
Ravi Kumar, Alexander Russell
SODA 1998
Ravi Kumar, Prabhakar Raghavan, et al.
ACM TOIT
Amir Abboud, Robert Krauthgamer, et al.
SODA 2020