---
_id: '18966'
abstract:
- lang: eng
  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.
author:
- first_name: Yossi
  full_name: Azar, Yossi
  last_name: Azar
- first_name: Edith
  full_name: Cohen, Edith
  last_name: Cohen
- first_name: Amos
  full_name: Fiat, Amos
  last_name: Fiat
- first_name: Haim
  full_name: Kaplan, Haim
  last_name: Kaplan
- first_name: Harald
  full_name: Racke, Harald
  last_name: Racke
citation:
  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>'
  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} }'
  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>.
  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.
  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>.
  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.'
date_created: 2020-09-03T14:34:33Z
date_updated: 2022-01-06T06:53:56Z
department:
- _id: '63'
doi: 10.1145/780542.780599
language:
- iso: eng
publication: Proceedings of the thirty-fifth ACM symposium on Theory of computing  -
  STOC '03
publication_identifier:
  isbn:
  - '1581136749'
publication_status: published
status: public
title: Optimal oblivious routing in polynomial time
type: conference
user_id: '15415'
year: '2003'
...