  For bin packing, the input consists of $n$ items with sizes $s_1,...,s_n \in
[0,1]$ which have to be assigned to a minimum number of bins of size 1.
Recently, the second author gave an LP-based polynomial time algorithm that
employed techniques from discrepancy theory to find a solution using at most
$OPT + O(\log OPT \cdot \log \log OPT)$ bins.
  In this paper, we present an approximation algorithm that has an additive gap
of only $O(\log OPT)$ bins, which matches certain combinatorial lower bounds.
Any further improvement would have to use more algebraic structure. Our
improvement is based on a combination of discrepancy theory techniques and a
novel 2-stage packing: first we pack items into containers; then we pack
containers into bins of size 1. Apart from being more effective, we believe our
algorithm is much cleaner than the one of Rothvoss.
