Shuchi Chawla, Anupam Gupta, Harald Räcke
In this paper, we study the metrics of negative type, which are metrics (V,d) such that √ d is an Euclidean metric; these metrics are thus also known as “ℓ2squared” metrics. We show how to...
DFG-Sonderforschungsbereich 376 and the IST Programme of the EU under contract number (2008)
Christof Krick, Friedhelm Meyer Heide, Harald Räcke, Berthold Vöcking, Matthias Westermann
This paper deals with data management for parallel and distributed systems. We present the DIVA (Distributed Variables) library that provides direct access to shared data objects from each node in a...
Shuchi Chawla, Anupam Gupta, Harald Räcke
In this paper, we study the metrics of negative type, which are metrics (V, d) such that √ d is an Euclidean metric; these metrics are thus also known as “ℓ2-squared” metrics. We show how to...
Abstract Minimizing Average Latency in Oblivious Routing (2008)
Prahladh Harsha, Thomas P. Hayes, Hariharan Narayanan, Harald Räcke, Jaikumar Radhakrishnan
We consider the problem of minimizing average latency cost while obliviously routing traffic in a network with linear latency functions. This is roughly equivalent to minimizing the function � e...
General General Terms Algorithms (2008)
Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke
A recent seminal result of Räcke is that for any network there is an oblivious routing algorithm with a polylog competitive ratio with respect to congestion. Unfortunately, Räcke’s construction...
Oblivious Routing on Node-Capacitated and Directed Graphs ∗ (2008)
Mohammad Thagi, Hajiaghayi Robert, D. Kleinberg, Tom Leighton, Harald Räcke
Oblivious routing algorithms for general undirected networks were introduced by Räcke [18], and this work has led to many subsequent improvements and applications. Comparatively little is known...
Abstract Minimizing Average Latency in Oblivious Routing (2008)
Prahladh Harsha, Thomas P. Hayes, Hariharan Narayanan, Harald Räcke, Jaikumar Radhakrishnan
We consider the problem of minimizing average latency cost while obliviously routing traffic in a network with linear latency functions. This is roughly equivalent to minimizing the function � e...
Shuchi Chawla, Anupam Gupta, Harald Räcke
In this paper, we study the metrics of negative type, which are metrics (V, d) such that √ d is an Euclidean metric; these metrics are thus also known as “ℓ2squared” metrics. We show how to...
Abstract Reducing State Changes with a Pipeline Buffer ∗ (2008)
Jens Krokowski, Harald Räcke, Christian Sohler, Matthias Westermann
A limiting factor in the performance of a rendering system is the number of state changes, i.e., changes of the attributes material, texture, shader program, etc., in the stream of rendered...
DFG-Sonderforschungsbereich 376 and the IST Programme of the EU under contract number (2008)
Christof Krick, Harald Räcke, Matthias Westermann
This paper deals with static data management in computer systems connected by networks. A basic functionality in these systems is the interactive use of shared data objects that can be accessed from...
General General Terms Algorithms (2008)
Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke
A recent seminal result of Räcke is that for any network there is an oblivious routing algorithm with a polylog competitive ratio with respect to congestion. Unfortunately, Räcke’s construction...
Improved embeddings of graph metrics into random trees (2006)
Kedar Dhamdhere, Anupam Gupta, Harald Räcke
Over the past decade, numerous algorithms have been developed using the fact that the distances in any n-point metric (V, d) can be approximated to within O(log n) by distributions D over trees on...
New lower bounds for oblivious routing in undirected graphs (2006)
Mohammad T. Hajiaghayi, Robert D. Kleinberg, Tom Leighton, Harald Räcke
Oblivious routing algorithms for general undirected networks were introduced by Räcke, and this work has led to many subsequent improvements and applications. Räcke showed that there is an...
Improved Embeddings of Graph Metrics into Random Trees (2006)
Kedar Dhamdhere Anupam, Anupam Gupta, Harald Räcke
Over the past decade, numerous algorithms have been developed using the fact that the distances in any n-point metric (V, d) can be approximated to within O(log n) by distributions over trees on the...
An O( √ n)-Approximation Algorithm For Directed Sparsest (2006)
Mohammadtaghi Hajiaghayi, Harald Räcke
We give an O ( √ n)-approximation algorithm for the Sparsest Cut Problem on directed graphs. A naïve reduction from Sparsest Cut to Minimum Multicut would only give an approximation ratio of O (...
New lower bounds for oblivious routing in undirected graphs (2006)
Mohammad T. Hajiaghayi, Robert D. Kleinberg, Tom Leighton, Harald Räcke
Oblivious routing algorithms for general undirected networks were introduced by Räcke, and this work has led to many subsequent improvements and applications. Räcke showed that there is an...
Oblivious network design (2006)
Anupam Gupta, Mohammad T. Hajiaghayi, Harald Räcke
Consider the following network design problem: given a network G = (V, E), source-sink pairs {si, ti} arrive and desire to send a unit of flow between themselves. The cost of the routing is this: if...
New lower bounds for oblivious routing in undirected graphs (2006)
Mohammad T. Hajiaghayi, Robert D. Kleinberg, Tom Leighton, Harald Räcke
Oblivious routing algorithms for general undirected networks were introduced by Räcke, and this work has led to many subsequent improvements and applications. Räcke showed that there is an...
Oblivious network design (2006)
Anupam Gupta, Mohammad T. Hajiaghayi, Harald Räcke
Consider the following network design problem: given a network G = (V, E), source-sink pairs {si, ti} arrive and desire to send a unit of flow between themselves. The cost of the routing is this: if...
Oblivious network design (2006)
Anupam Gupta, Mohammad T. Hajiaghayi, Harald Räcke
Consider the following network design problem: given a network G = (V, E), source-sink pairs {si, ti} arrive and desire to send a unit of flow between themselves. The cost of the routing is this: if...
Oblivious routing on node-capacitated and directed graphs (2005)
Mohammad T. Hajiaghayi, Robert D. Kleinberg, Tom Leighton, Harald Räcke
Oblivious routing algorithms for general undirected networks were introduced by Räcke [17], and this work has led to many subsequent improvements and applications. Comparatively little is known...
Miroslaw Korzeniowski, Jarek Kutyłowski, Peter Mahlmann, Harald Räcke, Kay Salzwedel, Christian Schindelhauer
I am grateful to my advisor, Friedhelm Meyer auf der Heide, who let me work at my own pace, steering the course of my work only slightly whenever it was needed. I really appreciate his trust and the...
Approximation Algorithms for Low-Distortion Embeddings Into Low-Dimensional Spaces (2005)
Mihai Bădoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, R. Ravi, ...
We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the two-dimensional plane. Among other results, we give an O ( √ n)-approximation...
Approximation Algorithms for Low-Distortion Embeddings Into Low-Dimensional Spaces (2005)
Mihai Bădoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, R. Ravi, ...
We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the two-dimensional plane. Among other results, we give an O ( √ n)-approximation...
Approximation Algorithms for Low-Distortion Embeddings Into Low-Dimensional Spaces (2005)
Mihai Bădoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, R. Ravi, ...
We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the two-dimensional plane. Among other results, we give an O ( √ n)-approximation...
Approximation Algorithms for Low-Distortion Embeddings Into (2005)
Mihai Bădoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, ...
We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the two-dimensional plane. Among other results, we give an O( # n)-approximation algorithm...
Oblivious routing on node-capacitated and directed graphs (2005)
Mohammadtaghi Hajiaghayi, Robert D. Kleinberg, Harald Räcke, Tom Leighton
Oblivious routing algorithms for general undirected networks were introduced by Räcke [Räcke 2002], and this work has led to many subsequent improvements and applications. Comparatively little is...
Oblivious routing on node-capacitated and directed graphs (2005)
Mohammad T. Hajiaghayi, Robert D. Kleinberg, Tom Leighton, Harald Räcke
Oblivious routing algorithms for general undirected networks were introduced by Räcke [17], and this work has led to many subsequent improvements and applications. Comparatively little is known...
Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut (2005)
Shuchi Chawla, Anupam Gupta, Harald Räcke
In this paper, we study the metrics of negative type, which are metrics (V,d) such that √ d is an Euclidean metric; these metrics are thus also known as “ℓ2squared” metrics. We show how to...
Balanced graph partitioning (2004)
Konstantin Andreev, Harald Räcke
We consider the problem of partitioning a graph into k components of roughly equal size while minimizing the capacity of the edges between different components of the cut. In particular we require...
Data Management in Networks: Experimental Evaluation of a Provably Good Strategy (2003)
Krick,Christof, Räcke,Harald, Vöcking,Berthold, Westermann,Matthias
Randomized Pursuit-Evasion in Graphs (2003)
Adler,Micah, Räcke,Harald, Sivadasan,Naveen, Sohler,Christian, Vöcking,Berthold
Data Management in Networks: Experimental Evaluation of a Provably Good Strategy (2003)
Krick, Christof, Räcke, Harald, Vöcking, Berthold, Westermann, Matthias
Randomized Pursuit-Evasion in Graphs (2003)
Adler, Micah, Räcke, Harald, Sivadasan, Naveen, Sohler, Christian, Vöcking, Berthold
Optimal oblivious routing in polynomial time (2003)
Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke
A recent seminal result of Räcke is that for any undirected network there is an oblivious routing algorithm with a polylogarithmic competitive ratio with respect to congestion. Unfortunately,...
Smoothed motion complexity (2003)
Valentina Damerow, Harald Räcke, Christian Scheideler, Christian Sohler
Abstract. We propose a new complexity measure for movement of objects, the smoothed motion complexity. Many applications are based on algorithms dealing with moving objects, but usually data of...
A Practical Algorithm for Constructing Oblivious Routing Schemes (2003)
Marcin Bienkowski, Miroslaw Korzeniowski, Harald Räcke, Harald R Acke
In a (randomized) oblivious routing scheme the path chosen for a request between a source s and a target t is independent from the current tra#c in the network. Hence, such a scheme consists of...
Optimal Oblivious Routing in Polynomial Time (2003)
Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke
A recent seminal result of Räcke is that for any network there is an oblivious routing algorithm with a polylog competitive ratio with respect to congestion. Unfortunately, Räcke's...
Randomized Pursuit-Evasion in Graphs (2002)
Adler,Micah, Räcke,Harald, Sivadasan,Naveen, Sohler,Christian, Vöcking,Berthold
{ We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a {\em hunter} and a {\em rabbit}. Let $G$ be any connected, undirected graph with $n$ nodes. The game is...
Randomized Pursuit-Evasion in Graphs (2002)
Adler, Micah, Räcke, Harald, Sivadasan, Naveen, Sohler, Christian, Vöcking, Berthold, Widmayer, Peter, ...
{ We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a {\em hunter} and a {\em rabbit}. Let $G$ be any connected, undirected graph with $n$ nodes. The game is...
Randomized pursuit-evasion in graphs (2002)
Micah Adler, Harald Räcke, Naveen Sivadasan, Christian Sohler, Berthold Vöcking
We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a hunter and a rabbit. Let G be any connected, undirected graph with n nodes. The game is played in rounds...
Online scheduling for sorting buffers (2002)
Harald Räcke, Christian Sohler, Matthias Westermann
Abstract. We introduce the online scheduling problem for sorting buffers. A service station and a sorting buffer are given. An input sequence of items which are only characterized by a specific...
Randomized pursuit-evasion in graphs (2002)
Micah Adler, Harald Räcke, Naveen Sivadasan, Christian Sohler, Berthold Vöcking
Abstract. We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a hunter and a rabbit. Let G be any connected, undirected graph with n nodes. The game is played...
Randomized pursuit-evasion in graphs (2002)
Micah Adler, Harald Räcke, Naveen Sivadasan, Christian Sohler, Berthold Vöcking
ns,voecking� Abstract. We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a hunter and a rabbit. Let � be any connected, undirected graph with � nodes....
Randomized pursuit-evasion in graphs (2002)
Micah Adler, Harald Räcke, Naveen Sivadasan, Christian Sohler, Berthold Vöcking
Abstract. We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a hunter and a rabbit. Let G be any connected, undirected graph with n nodes. The game is played...
Randomized pursuit-evasion in graphs (2002)
Micah Adler, Harald Räcke, Naveen Sivadasan, Christian Sohler, Berthold Vöcking
We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a hunter and a rabbit. Let be any connected, undirected graph with nodes. The game is played in rounds and...
Caching in Networks: Non-Uniform Algorithms and Memory Capacity Constraints (2000)
Matthias Westermann, Klaus Schröder, Harald Räcke, Matthias Westermann
First of all, I would like to thank my advisor Prof. Dr. Friedhelm Meyer auf der Heide for his great support. The atmosphere in his research group at Paderborn University was very creative. In...
Data Management in Networks: Experimental Evaluation of a Provably Good Strategy (1999)
Christof Krick, Harald Räcke, Berthold Vöcking, Matthias Westermann
This paper deals with data management for parallel and distributed systems in which the computing nodes are connected by a relatively sparse network. We present the DIVA (Distributed Variables)...