Optimal oblivious routing in polynomial time
Y. Azar, E. Cohen, A. Fiat, H. Kaplan, H. Racke, in: Proceedings of the Thirty-Fifth ACM Symposium on Theory of Computing - STOC ’03, 2003.
Download
No fulltext has been uploaded.
Conference Paper
| Published
| English
Author
Azar, Yossi;
Cohen, Edith;
Fiat, Amos;
Kaplan, Haim;
Racke, Harald
Abstract
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, Räcke's construction is not polynomial time. We give a polynomial time construction that guarantees Räcke's bounds, and more generally gives the true optimal ratio for any (undirected or directed) network.
Publishing Year
Proceedings Title
Proceedings of the thirty-fifth ACM symposium on Theory of computing - STOC '03
ISBN
LibreCat-ID
Cite this
Azar Y, Cohen E, Fiat A, Kaplan H, Racke H. Optimal oblivious routing in polynomial time. In: Proceedings of the Thirty-Fifth ACM Symposium on Theory of Computing - STOC ’03. ; 2003. doi:10.1145/780542.780599
Azar, Y., Cohen, E., Fiat, A., Kaplan, H., & Racke, H. (2003). Optimal oblivious routing in polynomial time. In Proceedings of the thirty-fifth ACM symposium on Theory of computing - STOC ’03. https://doi.org/10.1145/780542.780599
@inproceedings{Azar_Cohen_Fiat_Kaplan_Racke_2003, title={Optimal oblivious routing in polynomial time}, DOI={10.1145/780542.780599}, booktitle={Proceedings of the thirty-fifth ACM symposium on Theory of computing - STOC ’03}, author={Azar, Yossi and Cohen, Edith and Fiat, Amos and Kaplan, Haim and Racke, Harald}, year={2003} }
Azar, Yossi, Edith Cohen, Amos Fiat, Haim Kaplan, and Harald Racke. “Optimal Oblivious Routing in Polynomial Time.” In Proceedings of the Thirty-Fifth ACM Symposium on Theory of Computing - STOC ’03, 2003. https://doi.org/10.1145/780542.780599.
Y. Azar, E. Cohen, A. Fiat, H. Kaplan, and H. Racke, “Optimal oblivious routing in polynomial time,” in Proceedings of the thirty-fifth ACM symposium on Theory of computing - STOC ’03, 2003.
Azar, Yossi, et al. “Optimal Oblivious Routing in Polynomial Time.” Proceedings of the Thirty-Fifth ACM Symposium on Theory of Computing - STOC ’03, 2003, doi:10.1145/780542.780599.
Google Scholar
ISBN Search