Event Details
Optimality and Greed in Dynamic Allocation
Presenter: Peter Winkler - Bell Labs
Supervisor:
Date: Mon, March 17, 2003
Time: 13:30:00 - 00:00:00
Place: Cornett Building, Room A121
ABSTRACT
In dynamic storage allocation objects arrive according to some sort of random process, are assigned space in a facility, and terminate randomly, freeing space for further use. Constraints on space may sometimes force an arrival to be rejected, costing money.
Often in such a problem intuition tells us where in the facility to place an arrival, but it is notoriously difficult to prove that an on-line algorithm is best possible unless the process is completely specified. We will describe a new technique which can sometimes prove optimality without a specified arrival distribution, provided one assumes that it's wrong to reject an arrival when there is space for it. Problems to which this technique can be applied have already risen twice at Lucent Technologies; in each case we can show that if it's right to be greedy, then it's right to be space-efficient.
Dr. Peter Winkler is the Director of Fundamental Mathematics Research, Mathematical Sciences Research Centre, Bell Labs (Lucent Technologies), Murray Hill, New Jersey. His research interests are in discrete mathematics and the theory of computing; especially combinatorics, probability theory and applications. Dr. Winkler received his Ph.D. in Mathematics from Yale University in 1975. He is a member of the American Math Society, the Association for Computing Machinery, the Computing Research Association and the IEEE Computer Society.