[{"abstract":[{"text":"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.","lang":"eng"}],"publication":"Proceedings of the thirty-fifth ACM symposium on Theory of computing  - STOC '03","citation":{"chicago":"Azar, Yossi, Edith Cohen, Amos Fiat, Haim Kaplan, and Harald Racke. “Optimal Oblivious Routing in Polynomial Time.” In <i>Proceedings of the Thirty-Fifth ACM Symposium on Theory of Computing  - STOC ’03</i>, 2003. <a href=\"https://doi.org/10.1145/780542.780599\">https://doi.org/10.1145/780542.780599</a>.","short":"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.","ieee":"Y. Azar, E. Cohen, A. Fiat, H. Kaplan, and H. Racke, “Optimal oblivious routing in polynomial time,” in <i>Proceedings of the thirty-fifth ACM symposium on Theory of computing  - STOC ’03</i>, 2003.","apa":"Azar, Y., Cohen, E., Fiat, A., Kaplan, H., &#38; Racke, H. (2003). Optimal oblivious routing in polynomial time. In <i>Proceedings of the thirty-fifth ACM symposium on Theory of computing  - STOC ’03</i>. <a href=\"https://doi.org/10.1145/780542.780599\">https://doi.org/10.1145/780542.780599</a>","bibtex":"@inproceedings{Azar_Cohen_Fiat_Kaplan_Racke_2003, title={Optimal oblivious routing in polynomial time}, DOI={<a href=\"https://doi.org/10.1145/780542.780599\">10.1145/780542.780599</a>}, 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} }","ama":"Azar Y, Cohen E, Fiat A, Kaplan H, Racke H. Optimal oblivious routing in polynomial time. In: <i>Proceedings of the Thirty-Fifth ACM Symposium on Theory of Computing  - STOC ’03</i>. ; 2003. doi:<a href=\"https://doi.org/10.1145/780542.780599\">10.1145/780542.780599</a>","mla":"Azar, Yossi, et al. “Optimal Oblivious Routing in Polynomial Time.” <i>Proceedings of the Thirty-Fifth ACM Symposium on Theory of Computing  - STOC ’03</i>, 2003, doi:<a href=\"https://doi.org/10.1145/780542.780599\">10.1145/780542.780599</a>."},"type":"conference","department":[{"_id":"63"}],"date_created":"2020-09-03T14:34:33Z","publication_status":"published","date_updated":"2022-01-06T06:53:56Z","title":"Optimal oblivious routing in polynomial time","year":"2003","status":"public","publication_identifier":{"isbn":["1581136749"]},"author":[{"full_name":"Azar, Yossi","first_name":"Yossi","last_name":"Azar"},{"last_name":"Cohen","first_name":"Edith","full_name":"Cohen, Edith"},{"full_name":"Fiat, Amos","first_name":"Amos","last_name":"Fiat"},{"full_name":"Kaplan, Haim","first_name":"Haim","last_name":"Kaplan"},{"full_name":"Racke, Harald","last_name":"Racke","first_name":"Harald"}],"user_id":"15415","doi":"10.1145/780542.780599","language":[{"iso":"eng"}],"_id":"18966"}]