Peter Winkler, Bell Labs,

On the Optimality of Best Fit

Abstract: A vexing problem in the theory of computing is the difficulty of proving optimality of an on-line algorithm without assuming a particular probability distribution for input. I will describe what appears to be a new approach, applied to a simple dynamic packing problem which arose in the design of telephone equipment.

The novel feature is an assumption that optimal algorithms lie in a certain subclass. Optimality of the "obviously best" algorithm follows, in the case at hand, from combinatorial induction and an easy but weird coupling argument.