ONLINE LOAD BALANCING

被引：53

作者：

AZAR, Y

BRODER, AZ

KARLIN, AR

机构：

[1] DIGITAL SYST RES CTR,130 LYTTON AVE,PALO ALTO,CA 94301

[2] TEL AVIV UNIV,DEPT COMP SCI,IL-69978 TEL AVIV,ISRAEL

来源：

THEORETICAL COMPUTER SCIENCE | 1994年 / 130卷 / 01期

关键词：

Online greedy algorithms - Online load balancing - Randomized online algorithms - Servers - Tasks;

D O I：

10.1016/0304-3975(94)90153-8

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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, [(3n)2/3/2](1 + o(1)), and derive a lower bound, OMEGA(n1/2), for any other deterministic or randomized on-line algorithm.

引用

页码：73 / 84

页数：12

共 11 条

[1]

AZAR Y, 1992, 3RD P ANN ACM SIAM S, P203

[2]

AZAR Y, 1993, WORKSH ALG DAT STRUC, P119

[3]

BARTAL Y, 1992, 24TH P ACM S THEOR C, P51

[4]

BARUAH S, 1991, 32ND P ANN S F COMP, P100

[5]

Graham R. L., 1979, Discrete Optimisation, P287

[6] BOUNDS FOR CERTAIN MULTIPROCESSING ANOMALIES [J].

GRAHAM, RL .

BELL SYSTEM TECHNICAL JOURNAL, 1966, 45 (09) :1563-+

[7]

KARP R, 1990, 22ND P ANN ACM S THE, P352

[8] AN ONLINE GRAPH-COLORING ALGORITHM WITH SUBLINEAR PERFORMANCE RATIO [J].

LOVASZ, L ;

SAKS, M ;

TROTTER, WT .

DISCRETE MATHEMATICS, 1989, 75 (1-3) :319-325

[9]

PHILLIPS S, 1993, 25 ACM STOC, P402

[10]

SHMOYS D, 1991, 32ND P IEEE S F COMP, P131

← 1 2 →