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.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=3024508
بازگشت