29 citations · 51 across the 3 of their papers we have counts for
4 papers · 1 filter
Fault-Tolerant Spanners: Better and Simpler
Michael Dinitz, Robert Krauthgamer
A natural requirement of many distributed structures is fault-tolerance: after some failures, whatever remains from the structure should still be effective for whatever remains fro…
Directed Spanners via Flow-Based Linear Programs
Michael Dinitz, Robert Krauthgamer
We examine directed spanners through flow-based linear programming relaxations. We design an -approximation algorithm for the directed -spanner problem that works fo…
Streaming Algorithms from Precision Sampling
Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
A technique introduced by Indyk and Woodruff [STOC 2005] has inspired several recent advances in data-stream algorithms. We show that a number of these results follow easily from t…
Approximating Sparsest Cut in Graphs of Bounded Treewidth
Eden Chlamtac, Robert Krauthgamer, Prasad Raghavendra
We give the first constant-factor approximation algorithm for Sparsest Cut with general demands in bounded treewidth graphs. In contrast to previous algorithms, which rely on the f…