Asymmetric K-center Is log* H-hard to approximate
- Julia Chuzhoy
- Sudipto Guha
- et al.
- 2005
- Journal of the ACM
Publications
Date
Featured collections
Popular topics
30 results for Robert Krauthgamer
Cut-equivalent trees are optimal for min-cut queries
- Amir Abboud
- Robert Krauthgamer
- et al.
- 2020
- FOCS 2020
New algorithms and lower bounds for all-pairs max-flow in undirected graphs
- Amir Abboud
- Robert Krauthgamer
- et al.
- 2020
- SODA 2020
Faster algorithms for all-pairs bounded min-cuts
- Amir Abboud
- Loukas Georgiadis
- et al.
- 2019
- ICALP 2019
On sketching quadratic forms
- Alexandr Andoni
- Jiecao Chen
- et al.
- 2016
- ITCS 2016
Min-max graph partitioning and small set expansion
- Nikhil Bansal
- Uriel Feige
- et al.
- 2011
- FOCS 2011
How hard is it to approximate the best Nash equilibrium?
- Elad Hazan
- Robert Krauthgamer
- 2009
- SODA 2009
Greedy list intersection
- Robert Krauthgamer
- Aranyak Mehta
- et al.
- 2008
- ICDE 2008
The computational hardness of estimating edit distance
- Alexandr Andoni
- Robert Krauthgamer
- 2007
- FOCS 2007
On triangulation of simple networks
- Robert Krauthgamer
- 2007
- SPAA 2007