Harald Räcke
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Harald Räcke has a total of 12 co-authors. Here are the top co-authors by number of shared publications:
- Monika Henzinger
Institute of Science and Technology Austria, Klosterneuburg, Austria
3 shared publications - Stefan Schmid
TU Berlin & Weizenbaum Institute, Berlin, Germany
3 shared publications - Robin Münk
Technical University of Munich, Munich, Germany
2 shared publications - Ruslan Zabrodin
Technical University of Munich, Munich, Germany
2 shared publications - A. R. Sricharan
Doctoral School Computer Science DoCS, Faculty of Computer Science, University of Vienna, Vienna, Austria
1 shared publication - Anupam Gupta
New York University, New York, USA
1 shared publication
Latest Publications
- Open Access
- 6 July 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 22 (3) , 1-24
Incremental Approximate Maximum Flow via Residual Graph Sparsification
We give an algorithm that, with high probability, maintains a \((1-\varepsilon)\) -approximate \(s\text{-}t\) maximum flow in undirected, uncapacitated \( n \) -vertex graphs undergoing \( m \) edge insertions in \(\tilde{O}(m+nF^{*}/\varepsilon)\) total update time, where \(F^{*}\) is the maximum flow on the final graph. This is the first algorithm to achieve polylogarithmic amortized update time for dense graphs ( \(m=\Omega(n^{2})\) ), and more generally, for graphs where \(F^{*}=\tilde{O}(m/n)\) . At the heart of our incremental algorithm is the residual graph sparsification technique of Karger and Levine [STOC ’02, SICOMP ’15], originally designed for computing exact maximum flows in the static setting. Our main contributions are (i) showing how to maintain such sparsifiers for approximate maximum flows in the incremental setting and (ii) generalizing the cut sparsification framework of Fung et al. [STOC ’11, SICOMP ’19] from undirected graphs to balanced directed graphs.- 6 July 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 22 (3) , 1-24
Open AccessIncremental Approximate Maximum Flow via Residual Graph Sparsification
We give an algorithm that, with high probability, maintains a \((1-\varepsilon)\) -approximate \(s\text{-}t\) maximum flow in undirected, uncapacitated \( n \) -vertex graphs undergoing \( m \) edge insertions in \(\tilde{O}(m+nF^{*}/\varepsilon)\) total update time, where \(F^{*}\) is the maximum flow on the final graph. This is the first algorithm to achieve polylogarithmic amortized update time for dense graphs ( \(m=\Omega(n^{2})\) ), and more generally, for graphs where \(F^{*}=\tilde{O}(m/n)\) . At the heart of our incremental algorithm is the residual graph sparsification technique of Karger and Levine [STOC ’02, SICOMP ’15], originally designed for computing exact maximum flows in the static setting. Our main contributions are (i) showing how to maintain such sparsifiers for approximate maximum flows in the incremental setting and (ii) generalizing the cut sparsification framework of Fung et al. [STOC ’11, SICOMP ’19] from undirected graphs to balanced directed graphs. - Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1751-1762
Nonuniform Graph Partitioning with Just a Little Flex
In the nonuniform graph partitioning problem, we are given a capacitated graph G on n vertices, and numbers n1, n2, …, nk summing to n. The goal is to partition the vertices of G into parts S1, S2, …, Sk with |Si| = ni for each i, and minimizing the capacity of edges crossing between distinct parts. This generalizes, for instance, the well-known graph bisection problem. In order to obtain meaningful results, it is necessary to consider a bicriteria approximation, where we allow part sizes to be violated by a multiplicative factor є (i.e., |Si| ≤ (1 + є) ni for each i). If all part sizes are equal — uniform graph partitioning — an O(logn) approximation is possible for any constant є > 0, via a dynamic programming approach. But for nonuniform graph partitioning, no results were known without a substantial violation factor, the best result being an O(√lognlogk) approximation with є ≈ 5. Existing approaches to nonuniform graph partitioning seem to inherently rely on at least a factor 2 violation; whereas the dynamic programming approach for uniform graph partitioning do not extend. In this paper we take a completely different approach to give the first results for arbitrary small violation, showing an O(logn/є) approximation for any constant є > 0. Our approach involves a number of novel ingredients: a refinement of Räcke decomposition trees; a ”compression scheme” to decrease certain search spaces to polynomial size; a strong linear program based around local consistency within large neighborhoods; and a rounding scheme for this LP.
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1751-1762
Open AccessNonuniform Graph Partitioning with Just a Little Flex
In the nonuniform graph partitioning problem, we are given a capacitated graph G on n vertices, and numbers n1, n2, …, nk summing to n. The goal is to partition the vertices of G into parts S1, S2, …, Sk with |Si| = ni for each i, and minimizing the capacity of edges crossing between distinct parts. This generalizes, for instance, the well-known graph bisection problem. In order to obtain meaningful results, it is necessary to consider a bicriteria approximation, where we allow part sizes to be violated by a multiplicative factor є (i.e., |Si| ≤ (1 + є) ni for each i). If all part sizes are equal — uniform graph partitioning — an O(logn) approximation is possible for any constant є > 0, via a dynamic programming approach. But for nonuniform graph partitioning, no results were known without a substantial violation factor, the best result being an O(√lognlogk) approximation with є ≈ 5. Existing approaches to nonuniform graph partitioning seem to inherently rely on at least a factor 2 violation; whereas the dynamic programming approach for uniform graph partitioning do not extend. In this paper we take a completely different approach to give the first results for arbitrary small violation, showing an O(logn/є) approximation for any constant є > 0. Our approach involves a number of novel ingredients: a refinement of Räcke decomposition trees; a ”compression scheme” to decrease certain search spaces to polynomial size; a strong linear program based around local consistency within large neighborhoods; and a rounding scheme for this LP.
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1417-1428
An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time
A single-commodity congestion approximator for a graph is a compact data structure that approximately predicts the edge congestion required to route any set of single-commodity flow demands in a network. A hierarchical congestion approximator (HCA) consists of a laminar family of cuts in the graph and has numerous applications in approximating cut and flow problems in graphs, designing efficient routing schemes, and managing distributed networks. There is a tradeoff between the running time for computing an HCA and its approximation quality. The best polynomial-time construction in an n-node graph gives an HCA with approximation quality O(log1.5n loglogn). Among near-linear time algorithms, the best previous result achieves approximation quality O(log4 n). We improve upon the latter result by giving the first near-linear time algorithm for computing an HCA with approximation quality O(log2 n loglogn). Additionally, our algorithm can be implemented in the parallel setting with polylogarithmic span and near-linear work, achieving the same approximation quality. This improves upon the best previous such algorithm, which has an O(log9n) approximation quality. We also present a lower bound of Ω(logn) for the approximation guarantee of hierarchical congestion approximators. Crucial for achieving a near-linear running time is a new partitioning routine that, unlike previous such routines, manages to avoid recursing on large subgraphs. To achieve the improved approximation quality, we introduce the new concept of border routability of a cut and provide an improved sparsest cut oracle for general vertex weights.
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1417-1428
Open AccessAn Improved Quality Hierarchical Congestion Approximator in Near-Linear Time
A single-commodity congestion approximator for a graph is a compact data structure that approximately predicts the edge congestion required to route any set of single-commodity flow demands in a network. A hierarchical congestion approximator (HCA) consists of a laminar family of cuts in the graph and has numerous applications in approximating cut and flow problems in graphs, designing efficient routing schemes, and managing distributed networks. There is a tradeoff between the running time for computing an HCA and its approximation quality. The best polynomial-time construction in an n-node graph gives an HCA with approximation quality O(log1.5n loglogn). Among near-linear time algorithms, the best previous result achieves approximation quality O(log4 n). We improve upon the latter result by giving the first near-linear time algorithm for computing an HCA with approximation quality O(log2 n loglogn). Additionally, our algorithm can be implemented in the parallel setting with polylogarithmic span and near-linear work, achieving the same approximation quality. This improves upon the best previous such algorithm, which has an O(log9n) approximation quality. We also present a lower bound of Ω(logn) for the approximation guarantee of hierarchical congestion approximators. Crucial for achieving a near-linear running time is a new partitioning routine that, unlike previous such routines, manages to avoid recursing on large subgraphs. To achieve the improved approximation quality, we introduce the new concept of border routability of a cut and provide an improved sparsest cut oracle for general vertex weights.
- Open Access
- 16 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 240-254
Tight Bounds for Online Balanced Partitioning in the Generalized Learning Model
- 16 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 240-254
Open AccessTight Bounds for Online Balanced Partitioning in the Generalized Learning Model
- Open Access
- 24 August 2024
- Published by Association for Computing Machinery (ACM)
- p. 1016-1027
Expander Hierarchies for Normalized Cuts on Graphs
Expander decompositions of graphs have significantly advanced the understanding of many classical graph problems and led to numerous fundamental theoretical results. However, their adoption in practice has been hindered due to their inherent intricacies and large hidden factors in their asymptotic running times. Here, we introduce the first practically efficient algorithm for computing expander decompositions and their hierarchies and demonstrate its effectiveness and utility by incorporating it as the core component in a novel solver for the normalized cut graph clustering objective. Our extensive experiments on a variety of large graphs show that our expander-based algorithm outperforms state-of-the-art solvers for normalized cut with respect to solution quality by a large margin on a variety of graph classes such as citation, e-mail, and social networks or web graphs while remaining competitive in running time.
- 24 August 2024
- Published by Association for Computing Machinery (ACM)
- p. 1016-1027
Open AccessExpander Hierarchies for Normalized Cuts on Graphs
Expander decompositions of graphs have significantly advanced the understanding of many classical graph problems and led to numerous fundamental theoretical results. However, their adoption in practice has been hindered due to their inherent intricacies and large hidden factors in their asymptotic running times. Here, we introduce the first practically efficient algorithm for computing expander decompositions and their hierarchies and demonstrate its effectiveness and utility by incorporating it as the core component in a novel solver for the normalized cut graph clustering objective. Our extensive experiments on a variety of large graphs show that our expander-based algorithm outperforms state-of-the-art solvers for normalized cut with respect to solution quality by a large margin on a variety of graph classes such as citation, e-mail, and social networks or web graphs while remaining competitive in running time.
- Open Access
- 17 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 403-413
Polylog-Competitive Algorithms for Dynamic Balanced Graph Partitioning for Ring Demands
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 of self-adjusting infrastructures whose resources can be adjusted according to the workload they currently serve, in a demand-aware manner. Such dynamic adjustments can be exploited to improve network utilization and hence performance, by dynamically moving frequently interacting communication partners closer, e.g., collocating them in the same server or datacenter rack. In particular, we revisit the online balanced graph partitioning problem which captures the fundamental tradeoff between the benefits and costs of dynamically collocating communication partners. The demand is modelled as a sequence σ (revealed in an online manner) of communication requests between n processes, each of which is running on one of the ℓ servers. Each server has capacity k=n/ℓ, hence, the processes have to be scheduled in a balanced manner across the servers. A request incurs cost 1, if the requested processes are located on different servers, otherwise the cost is 0. A process can be migrated to a different server at cost 1. This paper presents the first online algorithm for online balanced graph partitioning achieving a polylogarithmic competitive ratio for the fundamental case of ring communication patterns. Specifically, our main contribution is a O(log3 n)-competitive randomized online algorithm for this problem. We further present a randomized online algorithm which is O(log2 n)-competitive when compared to a static optimal solution. Our two results rely on different algorithms and techniques and hence are of independent interest.
- 17 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 403-413
Open AccessPolylog-Competitive Algorithms for Dynamic Balanced Graph Partitioning for Ring Demands
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 of self-adjusting infrastructures whose resources can be adjusted according to the workload they currently serve, in a demand-aware manner. Such dynamic adjustments can be exploited to improve network utilization and hence performance, by dynamically moving frequently interacting communication partners closer, e.g., collocating them in the same server or datacenter rack. In particular, we revisit the online balanced graph partitioning problem which captures the fundamental tradeoff between the benefits and costs of dynamically collocating communication partners. The demand is modelled as a sequence σ (revealed in an online manner) of communication requests between n processes, each of which is running on one of the ℓ servers. Each server has capacity k=n/ℓ, hence, the processes have to be scheduled in a balanced manner across the servers. A request incurs cost 1, if the requested processes are located on different servers, otherwise the cost is 0. A process can be migrated to a different server at cost 1. This paper presents the first online algorithm for online balanced graph partitioning achieving a polylogarithmic competitive ratio for the fundamental case of ring communication patterns. Specifically, our main contribution is a O(log3 n)-competitive randomized online algorithm for this problem. We further present a randomized online algorithm which is O(log2 n)-competitive when compared to a static optimal solution. Our two results rely on different algorithms and techniques and hence are of independent interest.
- 1 February 2006
- Published by Elsevier in Information Processing Letters
- Vol. 97 (4) , 156-160
An -approximation algorithm for directed sparsest cut
- 1 February 2006
- Published by Elsevier in Information Processing Letters
- Vol. 97 (4) , 156-160
An -approximation algorithm for directed sparsest cut
- Open Access
- 1 January 2006
- Published by Association for Computing Machinery (ACM)
- p. 61-69
Improved embeddings of graph metrics into random trees
- 1 January 2006
- Published by Association for Computing Machinery (ACM)
- p. 61-69
Open AccessImproved embeddings of graph metrics into random trees