DIMACS Rutgers Seminar on Theoretical Computer Science

Title:

On the value of Planning and Capital

Speaker:

Sridhar Rajagopalan

DIMACS, Princeton University

Place:

Seminar Room 431, CoRE Building,

Busch Campus, Rutgers University.

Time:

10:00 AM - 11:00 AM

Wednesday, January 25, 1995

Abstract:

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)