Optimal oblivious routing in polynomial time
Yossi Azar, Edith Cohen, Amos Fiat, Haim Y. Kaplan, Harald Räcke · 2003
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.