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.