
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,��] for some ��\leq 1, yielding tight bounds for the Strong Price of Anarchy for all ��\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 ��\leq 1.
game theory, FOS: Computer and information sciences, price of anarchy, Combinatorial optimization, algorithm theory, Approximation methods and heuristics in mathematical programming, Approximation algorithms, bin packing, Computer Science - Computer Science and Game Theory, Computer Science - Data Structures and Algorithms, Combinatorial games, Data Structures and Algorithms (cs.DS), approximation algorithms, Computer Science and Game Theory (cs.GT)
game theory, FOS: Computer and information sciences, price of anarchy, Combinatorial optimization, algorithm theory, Approximation methods and heuristics in mathematical programming, Approximation algorithms, bin packing, Computer Science - Computer Science and Game Theory, Computer Science - Data Structures and Algorithms, Combinatorial games, Data Structures and Algorithms (cs.DS), approximation algorithms, Computer Science and Game Theory (cs.GT)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 25 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
