<p>Using Chandra's hint, I think I got the idea. We bounded the probability:</p>
<p><span class="math-container">$$Pr(G_i \leq b_i) \leq e^{-\frac{\rho(1-\frac{1}{\rho})^2 b_i}{3}}$$</span></p>
<p>Now consider an item of size <span class="math-container">$s_i$</span> that was left. It was left out because we didn't sample a configuration that contains it. This happens with probability</p>
<p><span class="math-container">$$(1-\sum_{j:{\bf T_j} \text{ contains item }i}\frac{x_j}{z^\ast})^{\rho z^\ast}\leq e^{-\rho}$$</span></p>
<p>Hence, using linearity of expectation, we expect at most <span class="math-container">$e^{-\rho}b_i$</span> items of size <span class="math-container">$s_i$</span> to be left out from the first sampling.</p>
<p>Now the final thing we need to do is to bound the <strong>expected</strong> total size of the remaining elements that were left out from the sampling. The bound is</p>
<p><span class="math-container">$$\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$$</span></p>
<p>We can then use any algorithm (say first fit) to approximate the remaining items in at most <span class="math-container">$$ 2e^{-\rho - \frac{ \rho(1-\frac{1}{\rho})^2 }{3}} OPT $$</span>
bins. Thus, we have used at most (on expectation)</p>
<p><span class="math-container">$$(\rho + 2e^{-\rho - \frac{ \rho(1-\frac{1}{\rho})^2 }{3}})OPT + 1$$</span></p>
<p>bins. If we set <span class="math-container">$\rho \in (1, 1.64)$</span>, then the algorithm is a <span class="math-container">$\Delta OPT+1$</span> (<span class="math-container">$\Delta&lt;2$</span>) approximation. For example, setting <span class="math-container">$\rho=1.2$</span>, we get a <span class="math-container">$1.785OPT + 1$</span> approximation.</p>

CC BY-SA 4.0
2021-06-22T00:21:36.520Z
2021-06-22T00:38:28.667Z
2021-06-22T00:38:28.667Z
user3508551
<p>I am currently stuck on <a href="https://www.designofapproxalgs.com/book.pdf" rel="noreferrer">Exercise 5.12</a> in this book, which is apparently an unpublished result of David P. Williamson according to the book notes.</p>
<p>The problem asks to use randomized rounding and first fit algorithm to give a randomized rounding for 1D bin packing that uses at most <span class="math-container">$\rho OPT + k$</span> bins, for some <span class="math-container">$\rho&lt;2$</span> and constant <span class="math-container">$k$</span>.</p>
<p>I decided to go with rounding the configuration LP which is as follows. Suppose there are <span class="math-container">$m$</span> possible sizes of the elements to be packed with <span class="math-container">$b_1$</span> of size <span class="math-container">$s_1$</span>, <span class="math-container">$b_2$</span> of size <span class="math-container">$s_2$</span>, ..., and <span class="math-container">$b_m$</span> of size <span class="math-container">$s_m$</span>. Let <span class="math-container">$\bf T_1, ..., T_n$</span> denote all the possible (possible exponential) configurations of bins satisfying <span class="math-container">$\sum_j t_{i,j}s_j \leq 1$</span>. Then the LP is</p>
<p><span class="math-container">\begin{array}{ll}
\text{minimize}  &amp; \displaystyle\sum_{j}x_j \\
\text{subject to}&amp; \displaystyle\sum_{j}x_j{\bf T_j} \geq {\bf b} \\
&amp; x_j \geq 0
\end{array}</span></p>
<p>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 <span class="math-container">$1$</span> using the ellipsoid method. So suppose we now have the (near)-optimal solution <span class="math-container">${\bf x}^\ast$</span> with at most <span class="math-container">$m$</span> non-zero entries. Let <span class="math-container">$z^\ast = \sum_{j}x_j^\ast$</span></p>
<p>Next, I thought about sampling <span class="math-container">$\rho z^\ast $</span> configurations independently with probability <span class="math-container">$\frac{x_j}{z^\ast}$</span>. Suppose they are <span class="math-container">$\bf R_1, R_2, ..., R_{\rho z^\ast }$</span> with <span class="math-container">${\bf G} = \sum_i \bf R_i$</span>
However, now we need to show that the constraints are satisfied with high probability. To do this, observe that</p>
<p><span class="math-container">$$\mathbb{E}({\bf G})=\mathbb{E}(\sum_{i}{\bf R_i})= \rho z^\ast \mathbb{E}({\bf R_i})\geq \rho {\bf b}$$</span></p>
<p>So for any size <span class="math-container">$i$</span>, we can use standard Chernoff bound to bound that the constraint is not satisfied, or namely that</p>
<p><span class="math-container">$$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}}$$</span></p>
<p><strong>And this is where I am stuck.</strong> The bound <span class="math-container">$b_i\geq 1$</span> is not strong enough to enable using the union bound to prove that all the inequalities (<span class="math-container">$m$</span> of them) are satisfied with high probability.</p>
<p>The only way I see fixing this issue is to only consider <span class="math-container">$b_i\geq \Omega(\log m)$</span> and handle all the sizes with <span class="math-container">$b_i&lt; O(\log m)$</span> separately, but that would affect the number of bins by an extra additive <span class="math-container">$O(m\log m)$</span> which isn't constant.</p>

CC BY-SA 4.0
2021-06-21T18:38:47.790Z
As the problem says you should try to use both rounding and a fixing algorithm. Estimate the expected total size of the items that are not satisfied and then pack them using first fit.
Chandra Chekuri
CC BY-SA 4.0
2021-06-22T00:21:55.830Z
@ChandraChekuri Thanks, I think I figured it out. Added an answer just for completion.
user3508551
<np-hardness><approximation-algorithms><packing><extremal-combinatorics><chernoff-bound>
$\rho OPT + k$ approximation for bin packing (Unpublished result of David P. Williamson)
user3508551
# $\rho OPT + k$ approximation for bin packing (Unpublished result of David P. Williamson)

(Asked by: username_0 on 2021-06-19)

I am currently stuck on [Exercise 5.12](https://www.designofapproxalgs.com/book.pdf) 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.

**Tags:** np-hardness, approximation-algorithms, packing, extremal-combinatorics, chernoff-bound
> **Comments:**
> **username_1**: As the problem says you should try to use both rounding and a fixing algorithm. Estimate the expected total size of the items that are not satisfied and then pack them using first fit.  
> **username_0**: @ChandraChekuri Thanks, I think I figured it out. Added an answer just for completion.  

---

## 1 answers

### Answer by username_0 on 2021-06-22. Score: 2

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.


---

