Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
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
Link zum Volltext
Quelle
EBSCOhost Business Source Ultimate
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.