$\rho OPT + k$ approximation for bin packing (Unpublished result of David P. Williamson)

Question

I am currently stuck on Exercise 5.12 in this book, which is apparently an unpublished result of David P. Williamson according to the book notes.

The problem asks to use randomized rounding and first fit algorithm to give a randomized rounding for 1D bin packing that uses at most $\rho OPT + k$ bins, for some $\rho<2$ and constant $k$.

I decided to go with rounding the configuration LP which is as follows. Suppose there are $m$ possible sizes of the elements to be packed with $b_1$ of size $s_1$, $b_2$ of size $s_2$, ..., and $b_m$ of size $s_m$. Let $\bf T_1, ..., T_n$ denote all the possible (possible exponential) configurations of bins satisfying $\sum_j t_{i,j}s_j \leq 1$. Then the LP is

\begin{array}{ll} \text{minimize} & \displaystyle\sum_{j}x_j \\ \text{subject to}& \displaystyle\sum_{j}x_j{\bf T_j} \geq {\bf b} \\ & x_j \geq 0 \end{array}

is a relaxation. Even though there is an exponential number of variables (one for each configuration), it is possible to solve this LP in polynomial time within an additive error of $1$ using the ellipsoid method. So suppose we now have the (near)-optimal solution ${\bf x}^\ast$ with at most $m$ non-zero entries. Let $z^\ast = \sum_{j}x_j^\ast$

Next, I thought about sampling $\rho z^\ast $ configurations independently with probability $\frac{x_j}{z^\ast}$. Suppose they are $\bf R_1, R_2, ..., R_{\rho z^\ast }$ with ${\bf G} = \sum_i \bf R_i$ However, now we need to show that the constraints are satisfied with high probability. To do this, observe that

$$\mathbb{E}({\bf G})=\mathbb{E}(\sum_{i}{\bf R_i})= \rho z^\ast \mathbb{E}({\bf R_i})\geq \rho {\bf b}$$

So for any size $i$, we can use standard Chernoff bound to bound that the constraint is not satisfied, or namely that

$$Pr(G_i \leq b_i) = Pr(G_i \leq (1-(1-\frac{1}{\rho})(\rho b_i))\leq e^{-\frac{\rho(1-\frac{1}{\rho})^2 b_i}{3}}$$

And this is where I am stuck. The bound $b_i\geq 1$ is not strong enough to enable using the union bound to prove that all the inequalities ($m$ of them) are satisfied with high probability.

The only way I see fixing this issue is to only consider $b_i\geq \Omega(\log m)$ and handle all the sizes with $b_i< O(\log m)$ separately, but that would affect the number of bins by an extra additive $O(m\log m)$ which isn't constant.

Answer 1

Using Chandra's hint, I think I got the idea. We bounded the probability:

$$Pr(G_i \leq b_i) \leq e^{-\frac{\rho(1-\frac{1}{\rho})^2 b_i}{3}}$$

Now consider an item of size $s_i$ that was left. It was left out because we didn't sample a configuration that contains it. This happens with probability

$$(1-\sum_{j:{\bf T_j} \text{ contains item }i}\frac{x_j}{z^\ast})^{\rho z^\ast}\leq e^{-\rho}$$

Hence, using linearity of expectation, we expect at most $e^{-\rho}b_i$ items of size $s_i$ to be left out from the first sampling.

Now the final thing we need to do is to bound the expected total size of the remaining elements that were left out from the sampling. The bound is

$$\sum_{i=1}^m e^{-\frac{\rho(1-\frac{1}{\rho})^2 b_i}{3}} \times e^{-\rho}b_i\times s_i \leq e^{-\rho - \frac{ \rho(1-\frac{1}{\rho})^2 }{3}} OPT$$

We can then use any algorithm (say first fit) to approximate the remaining items in at most $$ 2e^{-\rho - \frac{ \rho(1-\frac{1}{\rho})^2 }{3}} OPT $$ bins. Thus, we have used at most (on expectation)

$$(\rho + 2e^{-\rho - \frac{ \rho(1-\frac{1}{\rho})^2 }{3}})OPT + 1$$

bins. If we set $\rho \in (1, 1.64)$, then the algorithm is a $\Delta OPT+1$ ($\Delta<2$) approximation. For example, setting $\rho=1.2$, we get a $1.785OPT + 1$ approximation.