Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
On-Line Resource Management with Application to Routing and Scheduling
| |
|
On-Line Resource Management with Application to Routing and Scheduling
S. Leonardi1 and A. Marchetti-Spaccamela1
| (1) |
Dipartimento di Informatica e Sistemistica, Università di Roma ``La Sapienza,'' via Salaria 113, 00198-Roma, Italy. leon@dis.uniroma1.it,
marchetti@dis.uniroma1.it., IT |
Abstract. 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.
Key words. On-line algorithms, Competitive analysis, Routing, Scheduling, Linear programming.
Received December 18, 1996; revised March 2, 1997.
Fulltext Preview (Small, Large)
|
|
|
|
|
|