On-line resource management with application to routing and scheduling

作     者：Leonardi, S Marchetti-Spaccamela, A 

作者机构：Univ Rome La Sapienza Dipartimento Informat & Sistemist I-00198 Rome Italy 

出 版 物：《ALGORITHMICA》 (算法)

年 卷 期：1999年第24卷第1期

页      面：29-49页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：on-line algorithms competitive analysis routing scheduling linear programming 

摘      要：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.