On-line resource management with application to routing and scheduling

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 wid e class of on-line problems: shop scheduling, packet routing, and in genera l a class of packing and assignment problems. Previously studied problems a s on-line multiprocessor scheduling and on-line virtual circuit routing can also be modeled within this framework.