Bin Packing Wrapup
Today the ideas for bin-packing were the following:
We first solved the special case where all items were “large” (i.e., had size at least $\varepsilon$) and the number of distinct sizes were small (at most $D$). Then we showed that a basic solution to the LP had at most $D$ non-zero variables. (See below for another recap.) And hence rounding these variables up to the next integer gives us an integer solution with at most $LP + D \leq OPT + D$ bins. So we want $D$ to be small, ideally say $1/\varepsilon^2$.
Next, to get the number of distinct sizes to be $D$, we did a bucketing trick, where we sorted the items, put them into buckets of size $n/D$, and the size of each item in a bucket was changed to the size of the largest item in that bucket. Then we showed this increases OPT additively to $OPT + n/D$. If $D = 1/\varepsilon^2$, then $n/D = \varepsilon^2 n \leq \varepsilon Vol \leq \varepsilon OPT$. Here we used (again) that the item sizes are large. So we lost the $n/D \leq \varepsilon OPT$ term in this rounding.
Finally, extending to small items is easy. Once we have a solution with $(1+\varepsilon) OPT + O(1/\varepsilon^2)$ bins, we try to fill the small items where we can, and open new bins only when we need to. If we don’t open a new bin, we’re great! And if we open a new bin, consider the last bin opened. It was opened because every preceding bin was at least $(1-\varepsilon)$ full. So in this case we get a $\frac{OPT}{1-\varepsilon} + 1$ guarantee, which is at most $(1+ 2\varepsilon)OPT + 1$.
The Argument for Few Non-zeros
Observe that the LP had a large number of variables (let’s call this number $N$) each corresponding to some pattern, but only $D$ “non-trivial” constraints, and the rest $N$ were all non-negativity constraints. Consider a basic solution. By definition, there are $N$ linearly independent tight constraints at this point. Only $D$ of these can be non-trivial. So the other $N-D$ tight constraints must each say $x_i = 0$ for some $i$. This means $N-D$ variables are zero. And at most $D$ variables are non-zero, as claimed. (This argument is so simple and yet so powerful, it’s like magic!)
Other Sources for Approximation Algorithms
If you’re interested in more, we’ll have another lecture on Approximation Algorithms using Semidefinite Programming, next Monday. Or you can check out the book by David Williamson and David Shmoys [PDF], or these very visual lecture notes by Thomas Rothvoss, or these two old courses I taught in F05 and S08.