• DocumentCode
    2722991
  • Title

    A Polylogarithmic-Competitive Algorithm for the k-Server Problem

  • Author

    Bansal, N. ; Buchbinder, N. ; Madry, A. ; Naor, J.

  • Author_Institution
    IBM T. J. Watson, NY, USA
  • fYear
    2011
  • fDate
    22-25 Oct. 2011
  • Firstpage
    267
  • Lastpage
    276
  • Abstract
    We give the first polylogarithmic-competitive randomized algorithm for the k-server problem on an arbitrary finite metric space. In particular, our algorithm achieves a competitive ratio of Õ(log3 n log2 k) for any metric space on n points. This improves upon the (2k-1)-competitive algorithm of Koutsoupias and Papadimitriou (J. ACM 1995) whenever n is sub-exponential in k.
  • Keywords
    queueing theory; randomised algorithms; (2k-1) competitive algorithm; arbitrary finite metric space; k-server problem; polylogarithmic competitive randomized algorithm; Algorithm design and analysis; Extraterrestrial measurements; Probability distribution; Resource management; Servers; Vectors; competitive analysis; k-server problem; randomized algorithms;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on
  • Conference_Location
    Palm Springs, CA
  • ISSN
    0272-5428
  • Print_ISBN
    978-1-4577-1843-4
  • Type

    conf

  • DOI
    10.1109/FOCS.2011.63
  • Filename
    6108181
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2722991