• DocumentCode
    3024508
  • Title

    A better algorithm for uniform metrical task systems with few states

  • Author

    Bein, Wolfgang ; Larmore, Lawrence L. ; Noga, John

  • Author_Institution
    Sch. of Comput. Sci., Nevada Univ., Las Vegas, NV, USA
  • fYear
    2005
  • fDate
    7-9 Dec. 2005
  • Abstract
    We give a randomized algorithm (the "Wedge Algorithm") of competitiveness for any metrical task system on a uniform space of k points. This algorithm has better competitiveness than the Irani-Seiden algorithm if k is smaller than 108. The algorithm is better by a factor of 2 if k < 47.
  • Keywords
    computational complexity; randomised algorithms; Irani-Seiden algorithm; Wedge Algorithm; randomized algorithm; uniform metrical task systems; Chromium; Ice; online algorithms; randomized algorithms; task systems;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Parallel Architectures,Algorithms and Networks, 2005. ISPAN 2005. Proceedings. 8th International Symposium on
  • ISSN
    1087-4089
  • Print_ISBN
    0-7695-2509-1
  • Type

    conf

  • DOI
    10.1109/ISPAN.2005.5
  • Filename
    1575811
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3024508