3 papers
cs.DS2019
The Norms of Graph Spanners
Eden Chlamtáč, Michael Dinitz, Thomas Robinson
A -spanner of a graph is a subgraph in which all distances are preserved up to a multiplicative factor. A classical result of Althöfer et al. is that for every integ…
cs.DS2016
The Densest k-Subhypergraph Problem
Eden Chlamtáč, Michael Dinitz, Christian Konrad +2
The Densest -Subgraph (DS) problem, and its corresponding minimization problem Smallest -Edge Subgraph (SES), have come to play a central role in approximation algorith…
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…