DIMACS Princeton Theory Lunch
On the Optimality of Best Fit
- Peter Winkler
- Bell Laboratories
- Room 402, Computer Science (CS) Bldg, 35 Olden St.
- Princeton University, Princeton, NLJ
- 12:00 p.m. - Lunch will be served at ll:45 a.m.
- Thursday, December 12, 1996
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
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