Improvements in online bin packing

We make two crucial changes to that framework. First, some of the decisions of the algorithm will depend on exact sizes of items, instead of their rough sizes (called types), as done in SuperHarmonic. Furthermore, SuperHarmonic assigns items colors to control the packing process. In our framework, we postpone the coloring decision in order to be able to bound the number of bins where the optimal solution performs significantly better than our algorithm.

Finally, the analysis of our algorithm requires an additional step of marking items, which results in additional constraints in the linear program that describes the competitive ratio of the algorithm. We then solve this LP with the ellipsoid method, making use of a separation oracle.

In addition, we give a lower bound of 1.5766 for algorithms in our framework. This shows that fundamentally different ideas will be required to make further improvements.