An Introduction to Proof Techniques for Bin-Packing Approximation Algorithms

The aim in this brief tutorial extension of the survey in [GJ] will be to explain somewhat informally certain techniques that do enjoy a moderately broad applicability, while making it clear where the novelty and perhaps ingenuity of the approach to an individual problem may be required.

Abstract

Introductory Remarks — Upon introducing a seemingly small change or generalization into either the model or an approximation algorithm for a previously studied bin packing problem, it has been common to find that very little of the analysis of the original problem can be exploited in analyzing the new problem. Such experiences may suggest that the mathematics of bin packing does not contain a central, well-structured theory that provides powerful, broadly applicable techniques for the analysis of approximation algorithms. It would be difficult to repudiate completely such an observation, but we hope to show that the extent to which it is true is largely inevitable. Specifically, our aim in this brief tutorial extension of the survey in [GJ] will be to explain somewhat informally certain techniques that do enjoy a moderately broad applicability, while making it clear where the novelty and perhaps ingenuity of the approach to an individual problem may be required.