11 citations · 27 across the 17 of their papers we have counts for
Showing 2011Show all
2 papers · 1 filter
cs.CC2011★ 11 cited
Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems
Per Austrin, Toniann Pitassi, Yu Wu
We study the approximability of a number of graph problems: treewidth and pathwidth of graphs, one-shot black (and black-white) pebbling costs of directed acyclic graphs, and a var…
cs.CC2011
Inapproximability of NP-Complete Variants of Nash Equilibrium
Per Austrin, Mark Braverman, Eden Chlamtac
In recent work of Hazan and Krauthgamer (SICOMP 2011), it was shown that finding an $\eps$-approximate Nash equilibrium with near-optimal value in a two-player game is as hard as f…