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 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