Chapter 35, Problem 1P

a

Program Plan Intro

To prove the problem of determining the minimum number of bins required is NP-HARD.

Explanation of Solution

Suppose $S=\left\{x_1,x_2,\mathrm{.......},x{k}_{}\right\}$ and $x={\displaystyle \sum _{1\le i\le k}{x}_i}$ . It can be assumed that $t\ge \frac{x}{12}$ because the answer to and are the same (indeed if the answer is yes for. Then there exists $C^{\text{'}}$ such that ${\displaystyle \sum x_i=t}$ and then there is ${\displaystyle \sum _{x_i\in \left(S/S^{\text{'}}\right)}{x}_i=X-t}$ and so the answer is yes for. On the other hand if the answer is yes for , so if $t<x/12$ , it can be considered $t^{;}<x-t\ge x/2$ . Then compute $x={\displaystyle \sum _{1\le i\le k}{x}_i}$ and compare it with t .

Note that

  $\begin{array}{c}{\displaystyle \sum _{1\le i\le n}{S}_i}={\displaystyle \sum _{1\le i\le k}{x}_i/t}\\ =\frac{1}{t}{\displaystyle \sum _{1\le i\le n}{x}_i}+\left(2t-x\right)/t\\ =x/t+\left(2t-x\right)/2\\ =2\end{array}$

So, the answer of derived bin-packing problem can-not be less than 2 . First assume that the answer to the given instance of sub set -sum problem is “yes”.

Now, there is $S^{\text{'}}=\left\{x_{i1},x_{i2},\mathrm{.......},x{il}_{}\right\}$ so that ${\displaystyle \sum _{i\le j\le l}{x}_{ij}=t}$ . Thus, the result is ${\displaystyle \sum _{i\le j\le l}{S}_{ij}={\displaystyle \sum _{1<j<l}{x}_{ij}/t=t/t}=1}$ .

Now $\left\{S_{i1},S_{i2},\mathrm{.......},S{il}_{}\right\}$ can be packed in one bin and the remaining objects in the other bin (the sum of all object sizes is 2. So, the sum of remaining object sizes are1). Since it is known that the answer to this bin-packing problem can’t be less than 2, so the answer to it will be 2. Now assume that the answer to the derived instance of bin-packing problem is 2. Assume $\left\{S_{i1},S_{i2},\mathrm{.......},S{il}_{}\right\}$ be the sizes of the objects in one of two bins that does not contain the object with the size $S_{k+1}=\left(2t-x\right)/t$ we have ${\displaystyle \sum _{i\le j<l}{S}_{ij}=1}$

  $\Rightarrow {\displaystyle \sum _{1<j<l}{x}_{ij}/t=1}\Rightarrow {\displaystyle \sum _{1<j<l}{x}_{ij}=t}$ . So a subset $S^{\text{'}}=\left\{x_{i1},x_{i2},\mathrm{.......},x{il}_{}\right\}$ of S is found so that ${\displaystyle \sum _{1<j<l}{x}_{ij}=t}$ . Thus the answer to the given instance of the subset-sum problem is “yes”.

b

Program Plan Intro

To argue that the optimal number of bins required is at least $\lceil S\rceil$ .

Explanation of Solution

Consider the packing ofn objects with sizes $S_1,S_2,\mathrm{........},S_N$ intob bins. Let $S={\displaystyle \sum _{i=1}^N{S}_i}$

Let $e_1,e_2,\mathrm{........},e_b$ be the unused space in each bin and let $e={\displaystyle \sum _{i=1}^b{e}_i}$

Therefore,

  $\begin{array}{c}b=\frac{totalspaceinbins}{sizeofeachbin}\\ =\frac{spaceusedinbins+spaceunusedinbins}{1}\\ =S+e\\ \ge S(sincee\ge 0).\end{array}$

Since bis an integer number, $b\ge \left[S\right]$ . This is true in particular for the optimal solution $b^{*}\ge \left[S\right]$ .

c

Program Plan Intro

To argue that the first-fit heuristic leaves at most one bin less than half full.

Explanation of Solution

The first- fit heuristic places each object in the first available bin. Suppose by contradiction that two bins $b_i$ and $b_j$ are half full and supposei < j. All object in would fit into since both and are half full. Therefore, the first-fit heuristic would have placed these objects in $b_i$ . Therefore, it is not possible that two bins may be half empty under the first-fit heuristic.

d

Program Plan Intro

To prove that the number of bins used by the first-fit heuristic is never more than $\lceil 2S\rceil$

Explanation of Solution

Consider a bin- packing solution provided by the first-fit HEURISTIC.

Using similar notation as in (b) (let $S={\displaystyle \sum _{i=1}^N{S}_i}$ and $e={\displaystyle \sum _{i=1}^b{e}_i}$ )

  $\begin{array}{c}b=S+e\\ =S+{\displaystyle \sum _{i=1}^b{e}_i}\mathrm{.......}(1)\end{array}$

It can be assumed without loss of generality that $b\ge 2$ for the case whereb = 1 is easily satisfied. If all the bins are at least half full, then $b=S+e\le S+\frac{b}{2}$ which implies $b\le 2S\le \left[2S\right]$

e

Program Plan Intro

To prove an approximation ratio of 2 for the first-fit heuristic.

Explanation of Solution

Letb be the number of the bins used the first-fit HEURISTIC and let $b^{*}$ be the optimal number of bins. By part (d) $\left[S\right]\le b^{*}$ . Combining both inequalities, the result is $b\le 2S\le \left[2S\right]\le 2b^{*}$ , therefore $\frac{b}{b^{*}}\le 2$ that is, the approximation ratio is 2 .

e

Program Plan Intro

To give an efficient implementation of the first-fit heuristic, and analyze its running time.

Explanation of Solution

Algorithm First-fit $\left(n,S_1,S_2,\mathrm{........},S_N\right)$ :

1. $b\leftarrow 0$

2. initialize data structures

3. fori = 1 to ndo

4. letjbe the first bin that can fit objecti with size $S_i(*)$

5. ifjexists then

6. inserti at the list (list $L\left[i\right]$ of objects in bin)

7.update data structures

8.else

9.

  $b\leftarrow b+1$

10. insertiat the list $L\left[b\right]$

11.update data structures II

12.endif

13. endfor

Each of the above steps can be done in $O\left(\log b\right)$ basic steps. Therefore, the total running time for this algorithm is $O\left(n\log b\right)\le O\left(n\log h\right)$ .