DIMACS Rutgers Seminar on Theoretical Computer Science


On the value of Planning and Capital


Sridhar Rajagopalan
DIMACS, Princeton University


Seminar Room 431, CoRE Building,
Busch Campus, Rutgers University.


10:00 AM - 11:00 AM
Wednesday, January 25, 1995


We examine a familiar quandary in financial matters:- current shortage of cash often forces investment choices that are suboptimal in the long run. We model this situation and show both negative results, namely that in some situations, some inefficiency is unavoidable; and a positive result, an algorithm whose inefficiency, in all situations covered by our model, is bounded. We consider several examples, including some in which the resource to be optimized is not money but computation time. Among our examples is an application to the scheduling of maintenance operations for storage disks; and a problem of sequentially constructing Steiner trees.

(Joint work with Leonard J. Schulman, Weizmann Institute)

Document last modified on January 23, 1995