Online oblivious routing

N. Bansal, A. Blum, S. Chawla, A. Meyerson

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    18 Citations (Scopus)

    Abstract

    We consider an online version of the oblivious routing problem. Oblivious routing is the problem of picking a routing between each pair of nodes (or a set of flows), without knowledge of the traffic or demand between each pair, with the goal of minimizing the maximum congestion on any edge in the graph. In the online version of the problem, we consider a "repeated game" setting, in which the algorithm is allowed to choose a new routing each night, but is still oblivious to the demands that will occur the next day. The cost of the algorithm at every time step is its competitive ratio, or the ratio of its congestion to the minimum possible congestion for the demands at that time step.We present an algorithm that is (1+e) competitive with respect to the best algorithm that uses a single routing for the entire sequence of days (known as the optimal static routing). Our result is a strengthening of the recent result of Azar et al [4], who gave a polynomial time algorithm to find an oblivious routing with the best possible competitive ratio, in that our algorithm achieves a competitive ratio arbitrarily to close to that of Azar et al [4], while at the same time performing nearly as well as the optimal static routing for the given sequence of demands. Our work was done independently, but subsequent to that of Azar et al [4].
    Original languageEnglish
    Title of host publicationSPAA 2003 (Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms, San Diego CA, USA, June 7-9, 2003)
    Place of PublicationNew York
    PublisherAssociation for Computing Machinery, Inc
    Pages44-49
    ISBN (Print)1-58113-661-7
    Publication statusPublished - 2003

    Fingerprint Dive into the research topics of 'Online oblivious routing'. Together they form a unique fingerprint.

  • Cite this

    Bansal, N., Blum, A., Chawla, S., & Meyerson, A. (2003). Online oblivious routing. In SPAA 2003 (Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms, San Diego CA, USA, June 7-9, 2003) (pp. 44-49). Association for Computing Machinery, Inc.