DIMACS Princeton Theory Lunch
Title:
On the Optimality of Best Fit
Speaker:
- Peter Winkler
- Bell Laboratories
Place:
- Room 402, Computer Science (CS) Bldg, 35 Olden St.
- Princeton University, Princeton, NLJ
Time:
- 12:00 p.m. - Lunch will be served at ll:45 a.m.
- Thursday, December 12, 1996
Abstract:
The following straightforward dynamic allocation
problem arose in the design of telephone equipment,
and was brought to me by Barnet Schmidt of Lucent.
A certain facility consists of a number of "slots"
grouped into "bins" of some fixed number of slots
each. Each slot can handle one "call", each bin one
"trunk". Calls and bins arrive and depart randomly,
and must be assigned slots and bins (resp.) when
possible.
An obvious algorithm to perform these assignments
is Best Fit: trunks go anywhere, calls go into the
fullest bin with a free slot. The question is: under
what conditions is this algorithm optimal?
The "right" conditions turn out to be surprisingly
strong in some respects and oddly weak in others; and
the proof of optimality has been described as "weird."
See if you agree.
Document last modified on December 12, 1996