On Online Algorithms with Advice for the <i>k</i>-Server Problem

作     者：Renault, Marc P. Rosen, Adi 

作者机构：Univ Paris 07 LIAFA Paris France UPMC Paris France CNRS Paris France Univ Paris 07 Paris France 

出 版 物：《THEORY OF COMPUTING SYSTEMS》 (计算系统理论)

年 卷 期：2015年第56卷第1期

页      面：3-21页

核心收录：

学科分类：07[理学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 070101[理学-基础数学] 

基　　金：ANR project QRAC ANR project NeTOC 

主　　题：Online computation with advice k-server problem Online algorithms Competitive analysis 

摘      要：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 3a parts per thousand currency signba parts per thousand currency signlogk. This improves upon the result of Bockenhauer 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 Bockenhauer et al. Second, we give a 1-competitive online algorithm for finite trees which uses 2+2aOElog(p+1)aOE parts per thousand 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.