Details

Autor(en) / Beteiligte

• Renault, Marc P.
• Rosén, Adi

Titel

On Online Algorithms with Advice for the k-Server Problem

Ist Teil von

• Theory of computing systems, 2015-01, Vol.56 (1), p.3-21

Ort / Verlag

Boston: Springer US

Erscheinungsjahr

2015

Quelle

Business Source Ultimate【Trial: -2024/12/31】【Remote access available】

Beschreibungen/Notizen

• We consider the model of online computation with advice (Emek et al., Theor. Comput. Sci. 412(24): 2642–2656, 2011 ). In particular, we study the k -server problem under this model. We prove three upper bounds for this problem. First, we show a -competitive online algorithm for general metric spaces with b bits of advice per request, where 3≤ b ≤log k . This improves upon the result of Böckenhauer et al. (ICALP (1), Lecture Notes in Computer Science, vol. 6755, pp. 207–218, 2011 ). Moreover, we believe that our algorithm and our analysis are more intuitive and simpler than those of Böckenhauer et al. Second, we give a 1-competitive online algorithm for finite trees which uses 2+2⌈log( p +1)⌉ bits of advice per request, where p is the caterpillar dimension of the tree. Lastly, we present a variant of the algorithm for the tree that is optimal for the line with 1-bit of advice.