A Better Algorithm for Uniform Metrical Task Systems with Few States
Document Type
Conference Proceeding
Publication Date
1-16-2006
Publication Title
Parallel Architectures, Algorithms and Networks: ISPAN 2005 Proceedings
Volume
2005
First page number:
94
Last page number:
99
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 10/sup 8/. The algorithm is better by a factor of 2 if k < 47.
Language
english
Repository Citation
Bein, W.,
Larmore, L. L.,
Noga, J.
(2006).
A Better Algorithm for Uniform Metrical Task Systems with Few States.
Parallel Architectures, Algorithms and Networks: ISPAN 2005 Proceedings, 2005
94-99.
http://dx.doi.org/10.1109/ISPAN.2005.5