Affordable Access

Publisher Website

On-line load balancing

Authors
Journal
Theoretical Computer Science
0304-3975
Publisher
Elsevier
Publication Date
Volume
130
Issue
1
Identifiers
DOI: 10.1016/0304-3975(94)90153-8
Disciplines
  • Computer Science

Abstract

Abstract The setup for our problem consists of n servers that must complete a set of tasks. Each task can be handled only by a subset of the servers, requires a different level of service, and once assigned cannot be reassigned. We make the natural assumption that the level of service is known at arrival time, but that the duration of service is not. The on-line load balancing problem is to assign each task to an appropriate server in such a way that the maximum load on the servers is minimized. In this paper we derive matching upper and lower bounds for the competitive ratio of the on-line greedy algorithm for this problem, namely, [(3 n) 2 3 /2](1+o(1)), and derive a lower bound, Ω( n 1 2 ), for any other deterministic or randomized on-line algorithm.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

On-line load balancing made simple: Greedy strikes...

on Journal of Discrete Algorithms Jan 01, 2007

On-Line Load Balancing of Temporary Tasks

on Journal of Algorithms Jan 01, 1997

On-line load balancing of temporary tasks revisite...

on Theoretical Computer Science Jan 01, 2002
More articles like this..