24 citations · 28 across the 7 of their papers we have counts for
9 papers
Polylog-Competitive Algorithms for Dynamic Balanced Graph Partitioning for Ring Demands
Harald Räcke, Stefan Schmid, Ruslan Zabrodin
The performance of many large-scale and data-intensive distributed systems critically depends on the capacity of the interconnecting network. This paper is motivated by the vision…
Dynamic Maintenance of Monotone Dynamic Programs and Applications
Monika Henzinger, Stefan Neumann, Harald Räcke +1
Dynamic programming (DP) is one of the fundamental paradigms in algorithm design. However, many DP algorithms have to fill in large DP tables, represented by two-dimensional arrays…
It's Good to Relax: Fast Profit Approximation for Virtual Networks with Latency Constraints
Robin Münk, Matthias Rost, Stefan Schmid +1
This paper proposes a new approximation algorithm for the offline Virtual Network Embedding Problem (VNEP) with latency constraints. Given is a set of virtual networks with computa…
Compact Oblivious Routing in Weighted Graphs
Philipp Czerner, Harald Räcke
The space-requirement for routing-tables is an important characteristic of routing schemes. For the cost-measure of minimizing the total network load there exist a variety of resul…
The Expander Hierarchy and its Applications to Dynamic Graph Algorithms
Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak +1
We introduce a notion for hierarchical graph clustering which we call the expander hierarchy and show a fully dynamic algorithm for maintaining such a hierarchy on a graph with …
Online Weighted Degree-Bounded Steiner Networks via Novel Online Mixed Packing/Covering
Sina Dehghani, Soheil Ehsani, MohammadTaghi Hajiaghayi +3
We design the first online algorithm with poly-logarithmic competitive ratio for the edge-weighted degree-bounded Steiner forest(EW-DB-SF) problem and its generalized variant. We o…
Online Degree-Bounded Steiner Network Design
Sina Dahghani, Soheil Ehsani, MohammadTaghi Hajiaghayi +2
We initiate the study of degree-bounded network design problems in the online setting. The degree-bounded Steiner tree problem { which asks for a subgraph with minimum degree that…
Vertex Sparsification in Trees
Gramoz Goranci, Harald Raecke
Given an unweighted tree with terminals , we show how to obtain a -quality vertex flow and cut sparsifier with . We prove that our result is…
Vertex Sparsifiers: New Results from Old Techniques
Matthias Englert, Anupam Gupta, Robert Krauthgamer +3
Given a capacitated graph and a set of terminals , how should we produce a graph only on the terminals so that every (multicommodity) flow betwee…