---
# System prepended metadata

title: 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. <!-- page 3-->
:::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)

<!--
e.g.
$B_1 = \{\frac{1}{2} + \epsilon, \frac{1}{4} + \epsilon, \frac{1}{4} − 2\epsilon\}$
$B_2 = \{\frac{1}{4} + 2\epsilon, \frac{1}{4} + 2\epsilon, \frac{1}{4} − 2\epsilon, \frac{1}{4} − 2\epsilon\}$
-->

<!--
slightly worse bound in [this old paper](https://www.sciencedirect.com/science/article/pii/0196677485900185)
$FFD(I) \leq \frac{11}{9}OPT(I) + 3$

notice that the $\frac{11}{9}$ is a tight bound.
Which means there's no such $\alpha, \beta$
that $FFD(I) \leq \alpha OPT(I) + \beta$

to prove the mystery $[\frac{11}{9}]$ theory we will look into [this original paper](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)
