Selfish bin packing and the subset sum algorithm

bin. More than 35 years after its first mention in the literature, establishing the worst-case performance of this heuristic remains, surprisingly, an open problem.

Due to their simplicity and intuitive appeal, greedy algorithms are the heuristic of choice of many practitioners. Therefore, better understanding simple greedy heuristics is, in general, an interesting topic in its own right. Very recently, Epstein and Kleiman (Proc. ESA 2008, pages 368-380) provided another incentive to study the subset sum algorithm by showing that the Strong Price of Anarchy of the game
theoretic version of the bin-packing problem is precisely the approximation ratio of this heuristic.

In this talk I will present a tight analysis for the approximation ratio of the subset sum algorithm, yielding a tight bound on the SPoA for the bin packing game.

(joint work with L. Epstein and E. Kleiman)