Offline file assignments for online load balancing
Dütting P, Henzinger MH, Weber I. 2011. Offline file assignments for online load balancing. Information Processing Letters. 111(4), 178–183.
Download
No fulltext has been uploaded. References only!
Journal Article
| Published
| English
Scopus indexed
Author
Dütting, Paul;
Henzinger, MonikaISTA ;
Weber, Ingmar
Abstract
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.
Publishing Year
Date Published
2011-01-15
Journal Title
Information Processing Letters
Publisher
Elsevier
Volume
111
Issue
4
Page
178-183
ISSN
IST-REx-ID
Cite this
Dütting P, Henzinger MH, Weber I. Offline file assignments for online load balancing. Information Processing Letters. 2011;111(4):178-183. doi:10.1016/j.ipl.2010.11.022
Dütting, P., Henzinger, M. H., & Weber, I. (2011). Offline file assignments for online load balancing. Information Processing Letters. Elsevier. https://doi.org/10.1016/j.ipl.2010.11.022
Dütting, Paul, Monika H Henzinger, and Ingmar Weber. “Offline File Assignments for Online Load Balancing.” Information Processing Letters. Elsevier, 2011. https://doi.org/10.1016/j.ipl.2010.11.022.
P. Dütting, M. H. Henzinger, and I. Weber, “Offline file assignments for online load balancing,” Information Processing Letters, vol. 111, no. 4. Elsevier, pp. 178–183, 2011.
Dütting P, Henzinger MH, Weber I. 2011. Offline file assignments for online load balancing. Information Processing Letters. 111(4), 178–183.
Dütting, Paul, et al. “Offline File Assignments for Online Load Balancing.” Information Processing Letters, vol. 111, no. 4, Elsevier, 2011, pp. 178–83, doi:10.1016/j.ipl.2010.11.022.