Arrow Research search

Author name cluster

Harald Räcke

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

24 papers
1 author row

Possible papers

24

SODA Conference 2021 Conference Paper

The Expander Hierarchy and its Applications to Dynamic Graph Algorithms

  • Gramoz Goranci
  • Harald Räcke
  • Thatchaphol Saranurak
  • Zihan Tan

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 n vertices undergoing edge insertions and deletions using n o (1) update time. An expander hierarchy is a tree representation of graphs that faithfully captures the cut-flow structure and consequently our dynamic algorithm almost immediately implies several results including: 1. The first fully dynamic algorithm with n o (1) worst-case update time that allows querying n o (1) -approximate conductance, s-t maximum flows, and s-t minimum cuts for any given ( s, t ) in O (log 1/6 n ) time. Our results are deterministic and extend to multi-commodity cuts and flows. All previous fully dynamic (or even decremental) algorithms for any of these problems take Ω( n ) update or query time. The key idea behind these results is a fully dynamic algorithm for maintaining a tree flow sparsifier, a notion introduced by Räcke [FOCS'02] for constructing competitive oblivious routing schemes. 2. A deterministic fully dynamic connectivity algorithm with n o (1) worst-case update time. This significantly simplifies the recent algorithm by Chuzhoy et al. that uses the framework of Nanongkai, Saranurak, and Wulff-Nilsen [FOCS'17]. 3. A deterministic fully dynamic treewidth decomposition algorithm on constant-degree graphs with n o (1) worst-case update time that maintains a treewidth decomposition of width tw( G ) · n o (1) where tw( G ) denotes the treewidth of the current graph. This is the first non-trivial dynamic algorithm for this problem. Our technique is based on a new stronger notion of the expander decomposition, called the boundary-linked expander decomposition. This decomposition is more robust against updates and better captures clustering structure of graphs compared to the standard expander decomposition. Given that the expander decomposition has proved extremely useful in many fields, including approximation, sketching, distributed, and dynamic algorithms, we expect that our new notion will find more future applications.

Details

SODA Conference 2021 Conference Paper

Tight Bounds for Online Graph Partitioning

  • Monika Henzinger
  • Stefan Neumann 0003
  • Harald Räcke
  • Stefan Schmid 0001

We consider the following online optimization problem. We are given a graph G and each vertex of the graph is assigned to one of ℓ servers, where servers have capacity k and we assume that the graph has ℓ · k vertices. Initially, G does not contain any edges and then the edges of G are revealed one-by-one. The goal is to design an online algorithm ONL, which always places the connected components induced by the revealed edges on the same server and never exceeds the server capacities by more than ∊ k for constant ∊ > 0. Whenever ONL learns about a new edge, the algorithm is allowed to move vertices from one server to another. Its objective is to minimize the number of vertex moves. More specifically, ONL should minimize the competitive ratio: the total cost ONL incurs compared to an optimal offline algorithm OPT. The problem was recently introduced by Henzinger et al. (SIGMETRICS'2019) and is related to classic online problems such as online paging and scheduling. It finds applications in the context of resource allocation in the cloud and for optimizing distributed data structures such as union–find data structures. Our main contribution is a polynomial-time randomized algorithm, that is asymptotically optimal: we derive an upper bound of O (log ℓ + log k ) on its competitive ratio and show that no randomized online algorithm can achieve a competitive ratio of less than Ω(log ℓ + log k ). We also settle the open problem of the achievable competitive ratio by deterministic online algorithms, by deriving a competitive ratio of Θ( ℓ log k ); to this end, we present an improved lower bound as well as a deterministic polynomial-time online algorithm. Our algorithms rely on a novel technique which combines efficient integer programming with a combinatorial approach for maintaining ILP solutions. More precisely, we use an ILP to assign the connected components induced by the revealed edges to the servers; this is similar to existing approximation schemes for scheduling algorithms. However, we cannot obtain our competitive ratios if we run the ILP after each edge insertion. Instead, we identify certain types of edge insertions, after which we can manually obtain an optimal ILP solution at zero cost without resolving the ILP. We believe this technique is of independent interest and will find further applications in the future.

Details

FOCS Conference 2019 Conference Paper

Polylogarithmic Guarantees for Generalized Reordering Buffer Management

  • Matthias Englert
  • Harald Räcke
  • Richard Stotz

In the Generalized Reordering Buffer Management Problem (GRBM) a sequence of items located in a metric space arrives online, and has to be processed by a set of k servers moving within the space. In a single step the first b still unprocessed items from the sequence are accessible, and a scheduling strategy has to select an item and a server. Then the chosen item is processed by moving the chosen server to its location. The goal is to process all items while minimizing the total distance travelled by the servers. This problem was introduced in [Chan, Megow, Sitters, van Stee TCS 12] and has been subsequently studied in an online setting by [Azar, Englert, Gamzu, Kidron STACS 14]. The problem is a natural generalization of two very well-studied problems: the k-server problem for b=1 and the Reordering Buffer Management Problem (RBM) for k=1. In this paper we consider the GRBM problem on a uniform metric in the online version. We show how to obtain a competitive ratio of O(log k(log k+loglog b)) for this problem. Our result is a drastic improvement in the dependency on b compared to the previous best bound of O(√b log k), and is asymptotically optimal for constant k, because Ω(log k + loglog b) is a lower bound for GRBM on uniform metrics.

Details

SODA Conference 2017 Conference Paper

Reordering Buffers with Logarithmic Diameter Dependency for Trees

  • Matthias Englert
  • Harald Räcke

In the reordering buffer problem a sequence of items located in a metric space arrive online, and have to be processed by a single server moving within the metric space. At any point in time, the first k still unprocessed items from the sequence are available for processing and the server has to select one of these items and process it by visiting its location. The goal is to process all items while minimizing the total distance the server moves. Englert, Räcke, Westermann (STOC’07) gave a deterministic O ( D. log k )-competitive online algorithm for weighted tree metrics with hop-diameter D. We improve the analysis of this algorithm and significantly improve the dependency on D. Specifically, we show that the algorithm is in fact O (log D+log k )-competitive. Our analysis is quite robust. Even when an optimal algorithm, to which we compare the online algorithm, is allowed to choose between the first h > k unprocessed items, the online algorithm is still O (h· (log D+log h)/ k )- competitive. For H = (1 + ∊) · k, with constant ∊ > 0, this is optimal. Our results also imply better competitive ratio for general metric spaces, improving the randomized O (log n · log 2 k ) result for n -point metric spaces from STOC’07 to O (log n · log k ).

Details

SODA Conference 2014 Conference Paper

Computing Cut-Based Hierarchical Decompositions in Almost Linear Time

  • Harald Räcke
  • Chintan Shah
  • Hanjo Täubig

We present a fast construction algorithm for the hierarchical tree decompositions that lie at the heart of oblivious routing strategies and that form the basis for approximation and online algorithms for various cut problems in graphs. Given an undirected graph G = ( V, E, c ) with edge capacities, we compute a single tree T = ( V T, E T, c T ), where the leaf nodes of T correspond to nodes in G, such that the tree approximates the cut-structure of G up to a factor of (log 4 n ). The best existing construction by Harrelson, Hildrum, and Rao [12] just guarantees a polynomial running time but offers a better approximation guarantee of (log 2 n log log n ). Phrasing our results in terms of vertex sparsifiers, we obtain the following: For a graph G = ( V, E ) with a subset S of terminals, we compute a tree T with at most 2| S | vertices (and the leafs of T correspond to nodes in S ) such that T is a flow-sparsifier for S in G with quality (log 2 n log 2 k ), where | V | = n and | S | = k. The running time is (polylog n · T ( m, 1/log 3 n )) where T ( m, ∊ ) is the time for computing an approximate maxflow in a graph with m edges. The latter is almost linear due to the recent results of Sherman [23] and Kelner et al. [13].

Details

STOC Conference 2012 Conference Paper

Optimal online buffer scheduling for block devices

  • Anna Adamaszek
  • Artur Czumaj
  • Matthias Englert
  • Harald Räcke

We introduce a buffer scheduling problem for block operation devices in an online setting. We consider a stream of items of different types to be processed by a block device. The block device can process all items of the same type in a single step. To improve the performance of the system a buffer of size k is used to store items in order to reduce the number of operations required. Whenever the buffer becomes full a buffer scheduling strategy has to select one type and then a block operation on all elements with this type that are currently in the buffer is performed. The goal is to design a scheduling strategy that minimizes the number of block operations required. In this paper we consider the online version of this problem, where the buffer scheduling strategy must make decisions without knowing the future items that appear in the input stream. Our main result is the design of an O(log log k)-competitive online randomized buffer scheduling strategy. The bound is asymptotically tight. As a byproduct of our LP-based techniques, we obtain a randomized offline algorithm that approximates the optimal number of block operations to within a constant factor.

Details

STOC Conference 2011 Conference Paper

Almost tight bounds for reordering buffer management

  • Anna Adamaszek
  • Artur Czumaj
  • Matthias Englert
  • Harald Räcke

We give almost tight bounds for the online reordering buffer management problem on the uniform metric. Specifically, we present the first non-trivial lower bounds for this problem by showing that deterministic online algorithms have a competitive ratio of at least Ω(√{log k/log log k}) and randomized online algorithms have a competitive ratio of at least Ω(log log k), where k denotes the size of the buffer. We complement this by presenting a deterministic online algorithm for the reordering buffer management problem that obtains a competitive ratio of O(√log k), almost matching the lower bound. This improves upon an algorithm by Avigdor-Elgrabli and Rabani (SODA 2010) that achieves a competitive ratio of O(log k/ log log k).

Details

FOCS Conference 2009 Conference Paper

Oblivious Routing for the Lp-norm

  • Matthias Englert
  • Harald Räcke

Gupta et al. [GHR06] introduced a very general multi-commodity flow problem in which the cost of a given flow solution on a graph G=(V, E) is calculated by first computing the link loads via a load-function l, that describes the load of a link as a function of the flow traversing the link, and then aggregating the individual link loads into a single number via an aggregation function. In this paper we show the existence of an oblivious routing scheme with competitive ratio O(log n) and a lower bound of Omega(log n/log log n) for this model when the aggregation function agg is an L_p-norm. Our results can also be viewed as a generalization of the work on approximating metrics by a distribution over dominating tree metrics (see e. g. [Bar96, Bar98, FRT03]) and the work on minimum congestion oblivious routing [Rae02, HHR03, Rae08]. We provide a convex combination of trees such that routing according to the tree distribution approximately minimizes the L_p-norm of the link loads. The embedding techniques of Bartal [Bar96, Bar98] and Fakcharoenphol et al. [FRT03] can be viewed as solving this problem in the L_1-norm while the result of Räcke [Rae08] solves it for L_\infty. We give a single proof that shows the existence of a good tree-based oblivious routing for any L_p-norm. For the Euclidean norm, we also show that it is possible to compute a tree-based oblivious routing scheme in polynomial time.

Details

STOC Conference 2007 Conference Paper

Reordering buffers for general metric spaces

  • Matthias Englert
  • Harald Räcke
  • Matthias Westermann

In the reordering buffer problem, we are given an input sequence of requests for service each of which corresponds to a point in a metric space. The cost of serving the requests heavily depends on the processing order. Serving a request induces cost corresponding to the distance between itself and the previously served request, measured in the underlying metric space. A reordering buffer with storage capacity k can be used to reorder the input sequence in a restricted fashion so as to construct an output sequence with lower service cost. This simple and universal framework is useful for many applications in computer science and economics, e.g., disk scheduling, rendering in computer graphics, or painting shops in car plants. In this paper, we design online algorithms for the reordering buffer problem. Our main result is a strategy with a polylogarithmic competitive ratio for general metric spaces. Previous work on the reordering buffer problem only considered very restricted metric spaces. We obtain our result by first developing a deterministic algorithm for arbitrary weighted trees with a competitive ratio of O(D · log k), where D denotes the unweighted diameter of the tree, i.e., the maximum number of edges on a path connecting two nodes. Then we show how to improve this competitive ratio to O(log 2 k) for metric spaces that are derived from HSTs. Combining this result with the results on probabilistically approximating arbitrary metrics by tree metrics, we obtain a randomized strategy for general metric spaces that achieves a competitive ratio of O(log 2 k · log n) in expectation against an oblivious adversary. Here n denotes the number of distinct points in the metric space. Note that the length of the input sequence can be much larger than n.

Details

STOC Conference 2006 Conference Paper

Fast convergence to Wardrop equilibria by adaptive sampling methods

  • Simon Fischer 0001
  • Harald Räcke
  • Berthold Vöcking

We study rerouting policies in a dynamic round-based variant of a well known game theoretic traffic model due to Wardrop. Previous analyses (mostly in the context of selfish routing) based on Wardrop's model focus mostly on the static analysis of equilibria. In this paper, we ask the question whether the population of agents responsible for routing the traffic can jointly compute or better learn a Wardrop equilibrium efficiently. The rerouting policies that we study are of the following kind. In each round, each agent samples an alternative routing path and compares the latency on this path with its current latency. If the agent observes that it can improve its latency then it switches with some probability depending on the possible improvement to the better path.We can show various positive results based on a rerouting policy using an adaptive sampling rule that implicitly amplifies paths that carry a large amount of traffic in the Wardrop equilibrium. For general asymmetric games, we show that a simple replication protocol in which agents adopt strategies of more successful agents reaches a certain kind of bicriteria equilibrium within a time bound that is independent of the size and the structure of the network but only depends on a parameter of the latency functions, that we call the relative slope . For symmetric games, this result has an intuitive interpretation: Replication approximately satisfies almost everyone very quickly. In order to achieve convergence to a Wardrop equilibrium besides replication one also needs an exploration component discovering possibly unused strategies. We present a sampling based replication-exploration protocol and analyze its convergence time for symmetric games. For example, if the latency functions are defined by positive polynomials in coefficient representation, the convergence time is polynomial in the representation length of the latency functions. To the best of our knowledge, all previous results on the speed of convergence towards Wardrop equilibria, even when restricted to linear latency functions, were pseudopolynomial.In addition to the upper bounds on the speed of convergence, we can also present a lower bound demonstrating the necessity of adaptive sampling by showing that static sampling methods result in a slowdown that is exponential in the size of the network. A further lower bound illustrates that the relative slope is, in fact, the relevant parameter that determines the speed of convergence.

Details

STOC Conference 2003 Conference Paper

Optimal oblivious routing in polynomial time

  • Yossi Azar
  • Edith Cohen
  • Amos Fiat
  • Haim Kaplan
  • Harald Räcke

A recent seminal result of Racke is that for any network there is an oblivious routing algorithm with a polylog competitive ratio with respect to congestion. Unfortunately, Racke's construction is not polynomial time. We give a polynomial time construction that guarantee's Racke's bounds, and more generally gives the true optimal ratio for any network.

Details

FOCS Conference 2002 Conference Paper

Minimizing Congestion in General Networks

  • Harald Räcke

A principle task in parallel and distributed systems is to reduce the communication load in the interconnection network, as this is usually the major bottleneck for the performance of distributed applications. We introduce a framework for solving online problems that aim to minimize the congestion (i. e. the maximum load of a network link) in general topology networks. We apply this framework to the problem of online routing of virtual circuits and to a dynamic data management problem. For both scenarios we achieve a competitive ratio of O(log/sup 3/ n) with respect to the congestion of the network links. Our online algorithm for the routing problem has the remarkable property that it is oblivious, i. e. , the path chosen for a virtual circuit is independent of the current network load. Oblivious routing strategies can easily be implemented in distributed environments and have therefore been intensively studied for certain network topologies as e. g. meshes, tori and hypercubic networks. This is the first oblivious path selection algorithm that achieves a polylogarithmic competitive ratio in general networks.

Details
v2026.09.13