Offline file assignments for online load balancing

作     者：Duetting, Paul Henzinger, Monika Weber, Ingmar 

作者机构：Yahool Res Barcelona E-08003 Barcelona Spain Ecole Polytech Fed Lausanne Stn 14 CH-1015 Lausanne Switzerland Univ Vienna Fac Comp Sci A-1090 Vienna Austria 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：2011年第111卷第4期

页      面：178-183页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Load balancing On-line algorithms Information retrieval File distribution 

摘      要：We study a novel load balancing problem that arises in web search engines. The problem is a combination of an offline assignment problem, where files need to be (copied and) assigned to machines, and an online load balancing problem, where requests ask for specific files and need to be assigned to a corresponding machine, whose load is increased by this. We present simple deterministic algorithms for this problem and exhibit an interesting trade-off between the available space to make file copies and the obtainable makespan. We also give non-trivial lower bounds for a large class of deterministic algorithms and present a randomized algorithm that beats these bounds with high probability. (C) 2010 Elsevier B.V. All rights reserved.