Note on the work function algorithm

  • Béla Csaba

Abstract

We prove that the work function algorithm is (n-l)-competitive for the k-server problem, where n is the number of points in the metric space. This gives improved upper bounds when k +3 < n < 2k-1; in particular, it shows that the work function algorithm is optimal for k = n-1. Recently this result was proved independently by Koutsoupias in [K].

Downloads

Download data is not yet available.
Published
2000-01-01
How to Cite
Csaba, B. (2000). Note on the work function algorithm. Acta Cybernetica, 14(3), 503-506. Retrieved from https://cyber.bibl.u-szeged.hu/index.php/actcybern/article/view/3545
Section
Regular articles