Details

Autor(en) / Beteiligte

• Renault, Marc P.
• Rosén, Adi
• Solis-Oba, Roberto
• Persiano, Giuseppe

Titel

On Online Algorithms with Advice for the k-Server Problem

Ist Teil von

• Approximation and Online Algorithms, p.198-210

Ort / Verlag

Berlin, Heidelberg: Springer Berlin Heidelberg

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• We consider the model of online computation with advice [5]. In particular, we study the k-server problem under this model. We prove two upper bounds for this problem. First, we show a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\Big\lceil\frac{\lceil\log k\rceil}{b-2}\Big\rceil $\end{document}-competitive online algorithm for general metric spaces with b bits of advice per request, where 3 ≤ b ≤ logk. This improves upon the recent result of [1]. Moreover, we believe that our algorithm and our analysis are more intuitive and simpler than those of [1]. Second, we give a 1-competitive online algorithm for trees which uses 2 + 2⌈log(p + 1)⌉ bits of advice per request, where p is the caterpillar dimension of the tree.