  The subset sum algorithm is a natural heuristic for the classical Bin Packing
problem: In each iteration, the algorithm finds among the unpacked items, a
maximum size set of items that fits into a new 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
heuristics 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) 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 paper we establish the exact approximation ratio of the subset sum
algorithm, thus settling a long standing open problem. We generalize this
result to the parametric variant of the bin packing problem where item sizes
lie on the interval (0,\alpha] for some \alpha \leq 1, yielding tight bounds
for the Strong Price of Anarchy for all \alpha \leq 1. Finally, we study the
pure Price of Anarchy of the parametric Bin Packing game for which we show
nearly tight upper and lower bounds for all \alpha \leq 1.
