On-line restricted assignment of temporary tasks with unknown durations

被引：0

作者：

Armon, A

Azar, Y

Epstein, L ^{[1
]}

Regev, O

机构：

[1] Interdisciplinary Ctr, Sch Comp Sci, Herzliyya, Israel

[2] Tel Aviv Univ, Dept Comp Sci, IL-69978 Tel Aviv, Israel

[3] Inst Adv Study, Princeton, NJ 08540 USA

来源：

INFORMATION PROCESSING LETTERS | 2003年 / 85卷 / 02期

基金：

美国国家科学基金会; 以色列科学基金会;

关键词：

on-line algorithms; competitiveness; temporary tasks;

D O I：

10.1016/S0020-0190(02)00350-2

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We consider load balancing of temporary tasks on m machines in the restricted assignment model. It is known that the best competitive ratio for this problem is Theta(rootm). This bound is not achieved by the greedy algorithm whose competitive ratio is known to be Omega(m(2/3)). We give an alternative analysis to the greedy algorithm which is better than the known analysis for relatively small values of m. We also show that for a small number of machines, namely m less than or equal to 5, the greedy algorithm is optimal. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：67 / 72

页数：6

共 8 条

[1]

ARMON A, 2002, P 13 ANN ACM SIAM S

[2] On-line routing of virtual circuits with applications to load balancing and machine scheduling [J].