On-line resource management with application to routing and scheduling

被引：1

作者：

Leonardi, S ^{[1
]}

Marchetti-Spaccamela, A ^{[1
]}

机构：

[1] Univ Rome La Sapienza, Dipartimento Informat & Sistemist, I-00198 Rome, Italy

来源：

ALGORITHMICA | 1999年 / 24卷 / 01期

关键词：

on-line algorithms; competitive analysis; routing; scheduling; linear programming;

D O I：

10.1007/PL00009270

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We propose a framework to model on-line resource management problems based on an on-line version of positive linear programming. We consider both min cost problems and max benefit problems and propose logarithmic competitive algorithms that are optimal up to a constant factor. The proposed framework provides a general methodology that applies to a wide class of on-line problems: shop scheduling, packet routing, and in general a class of packing and assignment problems. Previously studied problems as on-line multiprocessor scheduling and on-line virtual circuit routing can also be modeled within this framework.

引用

页码：29 / 49

页数：21

共 30 条

[1]

Aspnes J., 1993, Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, P623, DOI 10.1145/167088.167248

[2]

AWERBUCH B, 1994, PROCEEDINGS OF THE FIFTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P321

[3]

Awerbuch B., 1993, Proceedings. 34th Annual Symposium on Foundations of Computer Science (Cat. No.93CH3368-8), P32, DOI 10.1109/SFCS.1993.366884

[4]

Awerbuch B., 1994, Proceedings. 35th Annual Symposium on Foundations of Computer Science (Cat. No.94CH35717), P412, DOI 10.1109/SFCS.1994.365675

[5]

AWERBUCH B, 1994, PROCEEDINGS OF THE FIFTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P312

[6]

Awerbuch B., 1996, Proceedings of the Fourth Israel Symposium on Theory of Computing and Systems, P37

[7]

Azar Y., 1992, Proceedings 33rd Annual Symposium on Foundations of Computer Science (Cat. No.92CH3188-0), P218, DOI 10.1109/SFCS.1992.267770

[8]

AZAR Y, 1992, PROCEEDINGS OF THE THIRD ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P203

[9]

Azar Y., 1993, Algorithms and Data Structures, P119

[10]

Bartal Y., 1996, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, P531, DOI 10.1145/237814.238001

← 1 2 3 →