Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(5)
Combinatorial Algorithm
Competitive Ratio
Oblivious Routing
Polynomial Time Algorithm
Probability Distribution
Related Publications
(5)
A polynomialtime tree decomposition to minimize congestion
Optimal oblivious routing in polynomial time
Minimizing Congestion in General Networks
On Clusterings  Good, Bad and Spectral
Finding effective supporttree preconditioners
Subscribe
Academic
Publications
A practical algorithm for constructing oblivious routing schemes
A practical algorithm for constructing oblivious routing schemes,10.1145/777412.777418,Marcin Bienkowski,Miroslaw Korzeniowski,Harald Räcke
Edit
A practical algorithm for constructing oblivious routing schemes
(
Citations: 64
)
BibTex

RIS

RefWorks
Download
Marcin Bienkowski
,
Miroslaw Korzeniowski
,
Harald Räcke
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 traffic in the network. Hence, such a scheme consists of probability distributions over st paths for every sourcetarget pair s,t in the network.In a recent result [11] it was shown that for any undirected network there is an
oblivious routing
scheme that achieves a polylogarithmic
competitive ratio
with respect to congestion. Subsequently, Azar et al. [4] gave a
polynomial time algorithm
that for a given network constructs the best
oblivious routing
scheme, i.e. the scheme that guarantees the best possible competitive ratio. Unfortunately, the latter result is based on the Ellipsoid algorithm; hence it is unpractical for large networks.In this paper we present a
combinatorial algorithm
for constructing an
oblivious routing
scheme that guarantees a
competitive ratio
of O(log4n) for undirected networks. Furthermore, our approach yields a proof for the existence of an
oblivious routing
scheme with
competitive ratio
O(log3n), which is much simpler than the original proof from [11].
Conference:
ACM Symposium on Parallel Algorithms and Architectures  SPAA
, pp. 2433, 2003
DOI:
10.1145/777412.777418
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
portal.acm.org
)
(
portal.acm.org
)
(
www.dcs.warwick.ac.uk
)
(
www.informatik.unitrier.de
)
(
wwwcs.unipaderborn.de
)
(
korzeniowski.im.pwr.wroc.pl
)
(
www.dcs.warwick.ac.uk
)
(
portal.acm.org
)
(
www2.cs.cmu.edu
)
(
www2.cs.unipaderborn.de
)
(
www.cs.cmu.edu
)
More »
Citation Context
(50)
...Optimal oblivious routing for general networks have been proposed but either require the solution of NPhard problems [8] or employ linear programming techniques that are too timeconsuming for largescale systems [
9
], [10]...
Jens Domke
,
et al.
DeadlockFree Oblivious Routing for Arbitrary Topologies
...
Bienkowski et al. 2003;
Borodin and Hopcroft 1985 ;G upta et al.2006; Räcke 2002; Valiant and Brebner 1981)...
Ayşegül Altın
,
et al.
OSPF routing with optimal oblivious performance ratio under polyhedral...
...Our approach is inspired by the cutbased graph decomposition of R¨ acke [18] that was developed in the context of oblivious routing schemes (see [19], [20], [
21
], [22] for some previous work on this subject)...
Aleksander Madry
.
Fast Approximation Algorithms for Cutbased Problems in Undirected Gra...
...Routing that is robust to changing and uncertain traffic demands is called oblivious routing [5], [9], [13], [14], [
15
]...
Eiji Oki
,
et al.
Fine TwoPhase Routing over Shortest Paths without Traffic Splitting
...Later it was followed by the polynomialtime algorithm in [2], [
3
]...
Marija Antic
,
et al.
Routing with load balancing: increasing the guaranteed node traffics
References
(17)
A polynomialtime tree decomposition to minimize congestion
(
Citations: 72
)
Chris Harrelson
,
Kirsten Hildrum
,
Satish Rao
Conference:
ACM Symposium on Parallel Algorithms and Architectures  SPAA
, pp. 3443, 2003
Tight bounds for oblivious routing in the hypercube
(
Citations: 61
)
Christos Kaldamanist
,
Danny Krizanc
,
Thanasis Tsantilas
Conference:
ACM Symposium on Parallel Algorithms and Architectures  SPAA
, pp. 3136, 1990
Exploiting locality for networks of limited bandwidth
(
Citations: 27
)
B. M. Maggs
,
F. Meyer Auf Der Heide
,
M. Westermann
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, 1997
Online load balancing with applications to machine scheduling and virtual circuit routing
(
Citations: 106
)
James Aspnes
,
Yossi Azart
,
Amos Fiat
,
Serge A. Plotkin
,
Orli Waarts
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 623631, 1993
Minimizing Congestion in General Networks
(
Citations: 115
)
Harald Räcke
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 4352, 2002
Sort by:
Citations
(64)
LoadBalanced ShortestPathBased Routing without Traffic Splitting in Hose Model
Shunichi Tsunoda
,
Abu Hena Al Muktadir
,
Eiji Oki
Published in 2011.
DeadlockFree Oblivious Routing for Arbitrary Topologies
Jens Domke
,
Torsten Hoefler
,
Wolfgang E. Nagel
Published in 2011.
OSPF routing with optimal oblivious performance ratio under polyhedral demand uncertainty
(
Citations: 3
)
Ayşegül Altın
,
Pietro Belotti
,
Mustafa Ç. Pınar
Journal:
Optimization and Engineering  OPTIM ENG
, vol. 11, no. 3, pp. 395422, 2010
Fast Approximation Algorithms for Cutbased Problems in Undirected Graphs
(
Citations: 1
)
Aleksander Madry
Journal:
Computing Research Repository  CORR
, vol. abs/1008.1, pp. 245254, 2010
Approximation Algorithms for the EdgeDisjoint Paths Problem via Raecke Decompositions
(
Citations: 1
)
Matthew Andrews
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 277286, 2010