approximation algorithm final report

# approximation algorithm final report ## The Bin Packing Problem ### First Fit Pretty straight forward, pick an item and find a bin for it by sequence. If it doesn't fit, open a new bin for it. **pros** easy to program. can be done in $O(n^2)$ with simple code. **proof this is a 2-approximation algorithm** :::info $k^* = OPT(I)$ $k =$ non-empty bins $I = \{i_1, i_2, ..., i_n\}, I \in (0, 1]$ $S(I) = \sum^{n}_{k = 1} i_k$ ::: We wants to show that :::success $k \leq 2 * k^* - 1$ ::: $K^* \geq \lceil S(I) \rceil \to$ We can obtain this pretty easy. $OPT(I) > \lceil S(I) \rceil$ is the definition of the optimal solution. $\lfloor \frac{k}{2} \rfloor \leq S(I)$ If a $i_n$ being put in bin k, which means there are no space for $i_n$ in $\{k-1, k - 2, ... 1\}$ bins therefore there must not be two bins with more than 0.5 space left. $\frac{k - 1}{2} \leq \lfloor \frac{k}{2} \rfloor \leq \lceil S(I) \rceil - 1$ $k \leq 2\lceil S(I) \rceil - 1$ $k \leq 2k^* - 1$ therefore >$k \leq 2 * k^* - 1$ is true For the ratio of this approximation $ratio = \frac{k}{k^*}$ $ratio = \frac{2k^* - 1}{k^*} = 2$ --- ### a tight bound of First Fit [pdf](https://iuuk.mff.cuni.cz/~sgall/ps/FFabs.pdf) weighting function ![](https://i.imgur.com/E2LbEt3.png) #### Lemma 1.1 Let $B, C$ be two bins in the FF packing such that $s(B) \geq \frac{2}{3}$, $C$ contain at least two items, and $B$ is opened before $C$ Then $$\frac{6}{5}s(B) + v(C) \geq 1$$ ##### $Proof$ C contain two items $\{c_1, c_2\}$ which don't fit into B. Thus we have $\{c_1, c_2\} > 1 - s(B)$. If $s(B) \geq \frac{5}{6}$, it become trivial to proof this lemma. In remaining case, let $x \in (0, \frac{1}{6}]$ such that $s(B) = \frac{5}{6} - x$. Thus $\{c_1, c_2\} > 1 - S(B) = 1 - (\frac{5}{6} - x) = \frac{1}{6} + x$ and we can obtain that $\{v(c_1), v(c_2)\} > \frac{3}{5}x$ We get $\frac{6}{5}s(B) + v(c_1) + v(c_2) > \frac{6}{5}(\frac{5}{6} - x) + \frac{3}{5}x + \frac{3}{5}x = 1$ --- Consider any FF-bin B with a single item. If $s(B) > 1/2$, then $v(B) = 0.4$ and $\frac{6}{5}s(B) + v(B) > 1$. Furthermore, at most one FF-bin has $s(B) ≤ 1/2$, by the definition of FF. --- ## First Fit Decreasing The item are ordered in a non-increasing order, and in this order the item always being packed into the first bin if possible. tight bound from [this reference](https://www.researchgate.net/publication/221444123_The_tight_bound_of_first_fit_decreasing_bin-packing_algorithm_is_FFDI_119_OPTI_69) :::info $$FFD(I) \leq \frac{11}{9}OPT(I) + \frac{6}{9}$$ ::: ### theorem 1.  :::info $$9FDD(L) \leq 11OPT(L) + 6$$ ::: #### $Proof$ It is trivial to proof, since $FFD() \& OPT()$ are integers. Instead of proving it, we are going to show $$9FFD(I) \geq 11OPT(I) + 7$$can't holds. where $I$ is a minimum counterexample --- we start from assuming $$9FFD(I) \geq 11OPT(I) + 7$$ is true $I$ indicates the minimal counterexample, i.e. contains the minimum numbers of items. therefore $$OPT(I) \geq 2\\FFD(I) \geq 3$$ must hold we denote the optimal bins as $B_i^*$ for $i = \{1, 2, ..., OPT(I)\}$, and the FFD bins as $B_i$ for $i = \{1, 2, ..., FFD(I)\}$ and sum of item being pack in to bins will be denote as $S(B_i)$ and $S(B_i^*)$, respectively. And for the counterexample we can have $B_{FFD(I)}$ contain only one item. let this item be denote as X. The item size is similar and denote as $s_k$ for $k = \{1, 2, ..., n\}$ and for the order is non-increasing, therefore $s_1 \geq s_2 \geq ... \geq s_n = S(X)$ For another denote as $A_{i, j}$, this is for representing the j-th item in $B_i$, and for the items in $B_i^*$(the OPT(I)) is denote as $A_{i, j}^*$. By this denotation we can say $A_{i, j_1} \geq A_{i, j_2}$, for $A_{i, j_1}$ comes into bin before $A_{i, j_2}$, which imply the order of these two element in $I$. This statement should be true in both $FFD(I) \& OPT(I)$. For a bin contain exactly i item, the bin will be called as i-bin. Because all items can fit into the OPT(I) bins, follow that$$\sum_{k = 1}^{n}s_k \leq OPT(I)$$ and note that X can't fit into any bins before $B_{FFD(I) - 1}$ thus we have $$S(B_i) + X > 1, i = \{1, 2, ...,FFD(I) - 1\}$$ --- ### Lemma 1. :::info $$X > \frac{FFD(I) - OPT(I) - 1}{FFD(I) - 2} \geq \frac{2}{11}$$ ::: #### $proof$ $\frac{FFD(I) - OPT(I) - 1}{FFD(I) - 2} \geq \frac{2}{11}$ is equivalent to >$$9FFD(I) \geq 11OPT(I) + 7$$ >$FFD(I) - OPT(I) - 1 \geq \frac{2FFD(I) - 4}{11}$ >$11FFD(I) - 11OPT(I) - 11 \geq 2FFD(I) - 4$ >$9FFD(I) - 11OPT(I) \geq 7$ we can rearrange $X + S(B_i) > 1$ to $S(B_i) > 1 - X$ And we notice that if there exist an X, for $S(B_1) > 1 - X$ must hold Thus we can have this statement $$OPT(I) \geq \sum^{OPT(I)}_{k = 1}s_k = X + S(B_1) + \sum^{FFD(I) - 1}_{i = 2} S(B_i) > 1 + (1 - X)(FFD(I) - 2)$$ $\sum^{OPT(I)}_{k = 1}s_k = X + S(B_1) + \sum^{FFD(I) - 1}_{i = 2} S(B_i)$ $\sum^{OPT(I)}_{k = 1}s_k$ is the size of items. If we count it by the item in the bins we can rewrite it as $X + S(B_1) + \sum^{FFD(I) - 1}_{i = 2} S(B_i)$ $X + S(B_1) + \sum^{FFD(I) - 1}_{i = 2} S(B_i) > 1 + (1 - X)(FFD(I) - 2)$ By the inequalities mention above. >$S(B_i) > 1 - X$ For every $i: i \in {1, 2, ... FFD(I)}$ the statement holds. Therefore every item in $\sum^{FFD(I) - 1}_{i = 2} S(B_i)$ should be greater than $(1 - X)$ thus we can said $\sum^{FFD(I) - 1}_{i = 2} S(B_i) >(1 - X)(FFD(I) - 2)$ --- ### Corollary 1. :::info $$X > \frac{\lceil \frac{11}{9}OPT(I) + \frac{7}{9} \rceil - OPT(I) - 1}{\lceil \frac{11}{9}OPT(I) + \frac{7}{9} \rceil - 2}$$ ::: #### $Proof$ apply >$$9FDD(L) \leq 11OPT(L) + 6$$ tied up this will have $$X > \frac{2}{11}\lceil(OPT(I) - 1)\rceil$$ from now we know for $OPT\&FFD$ can contain at most 5 item since $x > \frac{2}{11}$ is the smallest x we can have, means there are no item smaller than X. If a bin contain 6 item, the average item size will be $\frac{1}{6}$, which $X > \frac{2}{11} > \frac{1}{6}$ conflict the definition of X. --- ### Definition 1. We said that bin $B_i$ dominates the optimal bin $B^*_j$ for some $i$ and $j$. If for every item $s_i$ bring packed in $B^*_j$ there exists an item $s_l$ being packed in $B_i$ for which $s_i \leq s_l$ and these items in $B_i$ are different. --- ### Lemma 2. :::info There are no bins $B_i$ and $B^*_j$ such that $B_i$ dominate $B^*_j$. ::: #### $proof$ Swap one by one the items in $B^*_j$ by items of $B_i$ which dominate $B^*_j$. Then ignore the items in this bin we get a smaller counterexample, that is contradiction. --- ### Lemma 3. :::info Each optimal bin contains at least three items. ::: ## reference http://ac.informatik.uni-freiburg.de/lak_teaching/ws11_12/combopt/notes/bin_packing.pdf [The Tight Bound of First Fit Decreasing Bin-Packing Algorithm](https://www.researchgate.net/publication/221444123_The_tight_bound_of_first_fit_decreasing_bin-packing_algorithm_is_FFDI_119_OPTI_69) [Baker, B.S.: A new proof for the ﬁrst-ﬁt decreasing bin-packing algorithm. J. Algo-rithms (1985)](https://www.sciencedirect.com/science/article/pii/0196677485900185) https://en.wikipedia.org/wiki/First-fit-decreasing_bin_packing [Johnson, D.S.: Near-optimal bin-packing algorithms. Doctoral Thesis. MIT Press,Cambridge (1973)](https://dspace.mit.edu/bitstream/handle/1721.1/57819/17595570-MIT.pdf?sequence=2)   in page[273] ![](https://i.imgur.com/XP9ckV7.png) lemma 4.2 in page[168] ![](https://i.imgur.com/1R05Jpt.png) ![](https://i.imgur.com/1zAjnZp.png) ![](https://i.imgur.com/zt4HZPY.png) ![](https://i.imgur.com/IySgfHN.png)