Approximation Algorithms for Packing
This talk will discuss design and analysis techniques for bin-packing type
problems. We will review classical bin-packing algorithms, focusing on average-case
analysis, and present the "Sum-of-Squares" algorithm, a simple online algorithm
with great average-case performance. In terms of worst-case performance,
we will recall the classical approximation scheme of de la Vega and
Lueker and explore how it can be extended to several higher-dimensional
settings, and in particular present an asymptotic (i.e., as OPT/(maximum rectangle
height) goes to infinity) approximation scheme for dynamic storage allocation.