Minimizing Congestion in General Networks

By Harald Räcke. IEEE Annual Symposium on Foundations of Computer Science, 2002

302 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Optimal oblivious routing in polynomial time (2003, unknown): “In a recent paper, Räcke [9] gives the very surprising construction of a polylog competitive oblivious routing algorithm for general undirected networks.”
A Unified Approach to Approximating Partial Covering Problems (2006, methodology): “Based on Räcke’s hierarchical decomposition method [39], Alon, Awerbuch, Azar, Buchbinder and Naor [1] have shown how to simulate multicuts in general graphs by multicuts in the corresponding decomposition tree.”
Making intra-domain routing robust to changing and uncertain traffic demands: understanding fundamental tradeoffs (2003, background): “A recent breakthrough work by R¨acke [17] showed (existentially) a surprising upper bound: all symmetric networks (that is, networks where link capacities are the same in both directions, as is typically the case with large backbone networks) have a routing with an oblivious ratio that is at mos”
Optimal hierarchical decompositions for congestion minimization in networks (2008, methodology): “Wealso give improved guarantees for Minimum Bisection and Online Multicast Routing which are problems where the currently best known algorithms ([17] and [8]) do not depend on the hierarchical decomposition of Harrelson et al.”