The Robustness of the Sum-of-Squares Algorithm for Bin Packing

Bryan Bradley
Department of Computer Science
Hofstra University
bryan@sharpestknife.com

ABSTRACT Csirik et al presented in 1999 the Sum-of-Squares algorithm for online bin packing. They showed that (in the domain of discrete distributions) when the optimal expected waste is sublinear, SS also has sublinear expected waste. We will present our recent work dealing with variants of the algorithm. We will first discuss the online bin packing problem and some well-known approximation algorithms it, as well as metrics for evaluating the performance of such algorithms. Then we will present SS and our variants, Segregated Sum of Squares (SSS) and Sum of Squares Max (SSMax), which improve on the asymptotic running time of SS while appearing to give comparable average case results. We will conclude with the topic of further investigations into the area. This is joint work with Prof. Pillaipakkamnatt.