| General General Terms Algorithms (2008) | |||||||||||||||||
Abstract | |||||||||||||||||
| 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 is not polynomial time. We give a polynomial time construction that guarantee’s Räcke’s bounds, and more generally gives the true optimal ratio for any network. Categories and Subject Descriptors | |||||||||||||||||
Details der Publikation | |||||||||||||||||
| |||||||||||||||||