The Robustness of the Sum-of-Squares Algorithm for Bin Packing
Department of Computer Science
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.