This blog is still talking about “rounding data” strategy and dynamic programing. And this blog will focus on the bin-packing problem.

Backgroud

Definition of Bin-Packing

Given ${ n }$ items with size ${ a_1,a_2,\cdots,a_n }$, where ${ 1 \geq a_1 \geq a_2 \geq \cdots \geq a_n \geq 0 }$. We need pack the items into bins where each bin can hold any subset of items of total size as most ${ 1 }$. And we need to minimize the number of used bins.

Partition Problem ${ \leq_p }$ Bin-Packing

Partition Problem: Given ${ n }$ positive integers ${ b_1,b_2,\cdots, b_n }$, where ${ B = \sum{i=1}^n b_i }$ is even. It’s a decision problem that if we can partition the set ${ \{1,2,\cdots n\} }$ into two sets ${ S }$ and ${ T }$ s.t. ${ \sum_{i\in S} b_i = \sum_{i\in T} b_i}$. In fact, Partition Problem is a NP-Complete problem. (we don’t prove here).

Now we will show Partition Problem ${ \leq_p }$ Bin-Packing.

We set ${ a_i = 2b_i /B }$, and use algorithm of Bin-Packing to check if we can pack all pieces into two bins.

Asymptotic PTAS for Bin-Packing

Definition of APTAS

Definition: An asymptotic polynomial time approximation scheme (APTAS) is a family of algorithms ${ A_{\epsilon} }$, along with a constant ${ c }$, where there is an algorithm for each ${ \epsilon \geq 0}$, such that ${ A_{\epsilon} }$ is a ${(1+\epsilon)+c }$-approximation algorithm (for minimization problems) or a ${(1-\epsilon)-c }$-approximation algorithm (for maximization problems)

Big picture of idea

The Dynamic Programming strategy used in schueduling jobs on ${ m }$ machine inspires us. Giving target time equals to the limit of bins as ${ 1 }$. And here we need to figure out the minimum bins to be used.

Addtionally, we also divide the pieces into large and small ones.

1. Suppose we have an algorithm that can pack large pieces in at most ${ (1+\epsilon)OPT + 1 }$ bins. And we will show we can still use at most ${ (1+\epsilon)OPT + 1 }$ bins after packing the remaining small pieces.

2. We still use the rounding strategy for following dynamic Programming, and we will show the relation between rounded instance ${ I’ }$ and original input ${ I }$ satisfying ${ OPT(I’) \leq OPT(I) \leq OPT(I’) + k}$, ${ k }$ is a given constant depending on ${ \epsilon }$

3. We will show the Dynamic Programming will finish in polynomial time.

Large and small pieces

We define that a piece ${ i }$ is large if ${ a_i \geq \epsilon /2 }$, else call it small one.

• Step 1: Find packing for large items in at most ${ (1+\epsilon)OPT + 1 }$ bins.

• Step 2: Sort the small pieces in non-increasing order as their size.

• Step 3: Use first-fit algorithm, that is pick each item one by one and pack it to first bin in which it can fit.

Lemma 1: Suppose packing for large items is in at most ${ (1+\epsilon)OPT + 1 }$ bins, the above APTAS gives an ${ (1+\epsilon)OPT + 1 }$-approximation algorithm.

Proof. If there no extra bins used in step 3. The algorithm gives an ${ (1+\epsilon)OPT + 1 }$-approximation.

If there exists a new bin used in step 3. Let’s denote the total used bins is ${ k+1 }$. That means when placing some piece, it can not fit in any fist ${ k }$ bins, which leads to the using of ${ (k+1)^{\text{th}} }$ bin. Hence, we have each first ${ k }$ bins must be occupied at least ${ 1- \epsilon /2}$ size, otherwise, we can pack a small piece into it. Let’s denote the input as ${ I }$, and the total size as ${ SIZE(I) = \sum{i=1}^n a_i }$. So, ${ SIZE(I) \geq \left(1-\frac{\epsilon}{2}\right) k }$. Hence, we have

$$ k \leq \frac{SIZE(I)}{\left(1-\frac{\epsilon}{2}\right)} \leq \left(1 + \frac{\epsilon / 2}{1 - \epsilon / 2} \right) SIZE(I) \leq \left(1 + \frac{\epsilon}{2 - \epsilon} \right) SIZE(I) \leq (1+\epsilon) SIZE(I) $$

And, we know the ${ OPT(I) \geq SIZE(I) }$ (we must use bins that is greater than the total size of all pieces.) Thus, we got

$$ k+1 \leq (1+\epsilon) SIZE(I) + 1 \leq (1+\epsilon) OPT(I) + 1 $$

We prove the lemma 1. ${ \square }$

Rounding Large Items

Given a integer parameter ${ k }$, we round the pieces in following way

1. Group the pieces as

   • Group 1: first ${ k }$ largest pieces.

   • Group 2: second ${ k }$ largest pieces.

         ${ \vdots }$

   • Group ${ i }$: ${ i^{\text{th}} }$ ${ k }$ largest pieces.

         ${ \vdots }$

   • Last Group: remiaing ${ h }$ smallest pieces, where ${ h \leq k }$

2. Discard the Group 1.

3. For each group ${ i }$, round the pieces in group ${ i }$ as the largest-size piece.

Lemma 2: Denote the original input as ${ I }$ and rounded input as ${ I’ }$, we have

$$ OPT(I') \leq OPT(I) \leq OPT(I') + k $$

Proof. For the first inequality, if we have a packing of ${ I }$. We can still group them, and applythe packing of group ${ i }$ in ${ I }$ to group ${ i }$ in ${ I’ }$. Because ${ I’ }$ discards the first group, so we can group ${ i }$ in ${ I’ }$ can fit the positions of group ${ i }$ in ${ I }$. It’s clear that, ${ OPT(I’) \leq OPT(I) }$.

For second inequality, if we have a packing of ${ I’ }$. We keep the original positions of each pieces in ${ I }$, and we use at most ${ k }$ bins to contain the discarding first ${ k }$ pieces. That implies the ${ OPT(I) \leq OPT(I’) + k}$. ${ \square }$

Corollary: If we set ${ k = \lfloor \epsilon SIZE(I) \rfloor }$, suppose we find the optimal packing for ${ I’ }$, we will have ${ (1+\epsilon) OPT(I) }$-approximation for ${ I }$.

Proof. By Lemma 2, ${ OPT(I’) + k = OPT(I’) + \lfloor \epsilon SIZE(I) \rfloor \leq OPT(I) + \epsilon SIZE(I) \leq OPT(I) + \epsilon OPT = (1+\epsilon) OPT(I) }$. ${ \square }$

Dynamic Programming

We know the ${ 1 \leq OPT \leq n }$, so we can call Dynamic Programming at most ${ n }$ times to decide the ${ OPT(I’) }$. (By using bisearch, we can do ${ \ln n }$).

Following, we will show DP can finish in polynomial time. Recall DP in previous blog, we just need to show (1) The number of distinct item sizes is constant (like ${ r }$ is constant) (2) The number of large rounded pieces per bin is a constant.

Claim 1: The number of larege rounded jobs per bin is a constant.

Proof. Large pieces have size at least ${ \epsilon /2 }$. So, larege rounded jobs per bin is ${ 2 / \epsilon }$ is a constant. ${ \square }$

Claim 2: The number of distinct item sizes is constant

Proof. First we have ${ SIZE(I) \geq n \epsilon /2 }$, because each large pieces have size at least ${ \epsilon /2 }$. And the distinct size is ${ \Bigl\lceil \frac{n}{k} \Bigr\rceil -1 = \Bigl\lfloor \frac{n}{k} \Bigr\rfloor \leq \frac{n}{k} = \frac{n}{\lfloor \epsilon SIZE(I) \rfloor }}$

• If ${ \epsilon SIZE(I) <1 }$, we know there at most ${ \frac{SIZE(I)}{ \epsilon /2} \leq \frac{1/\epsilon}{\epsilon /2} = \frac{2}{\epsilon^2}}$. We don’t need to round them, we can just use DP (that is ${ k=1 }$).

• If ${ \epsilon SIZE(I) \geq 1 }$, (we know ${ \lfloor \alpha \rfloor \geq \frac{\alpha}{2} }$) we have

$$ \Bigl\lceil \frac{n}{k} \Bigr\rceil -1 = \Bigl\lfloor \frac{n}{k} \Bigr\rfloor \leq \frac{n}{k} = \frac{n}{\lfloor \epsilon SIZE(I) \rfloor } \leq \frac{n}{\epsilon SIZE(I)} \leq \frac{n}{\lfloor \epsilon SIZE(I) \rfloor } \leq \frac{n}{\epsilon SIZE(I) / 2} \leq \frac{n}{(n \epsilon /2)/2} = \frac{4}{\epsilon^4} $$

Hence we prove claim 2. ${ \square }$

Furthermore, we can have ${ \vert \mathcal{C} \vert \leq O\left(\frac{1}{\epsilon^2}\right)^{2 / \epsilon}}$ (the distinct sizes is ${ \frac{2}{\epsilon^2} }$ or ${\frac{4}{\epsilon^2} }$).

And we know ${ \hat{n_i} \leq k }$, so the DP take at most ${ k \cdot O\left(\frac{1}{\epsilon^2}\right) = O\left(\frac{SIZE(I)}{\epsilon}\right) \leq O\left(\frac{n}{\epsilon}\right)}$ iterations.