1BP: harmonic grouping

Dependencies:

1. Bin packing and Knapsack
2. Bin packing: predecessor of an input instance
3. Bin packing: union of input instances
4. Harmonic bound for fraction
5. Simple bound on harmonic sum
6. Bound on k extreme values

Let $I$ be an input instance for 1D bin packing $$ such that $\mathrm{size}(I)-min(I)\ge 2$.

The harmonic grouping scheme is an algorithm that first splits $I$ into disjoint instances $I^{\prime }$ and $I_2$ such that $\mathrm{size}(I_2)\le 3\ln (\frac{3}{min(I)})+\frac{9}{2}$. It then increases the item sizes in $I^{\prime }$ to get $I_1$ such that $I_1$ has at most $\mathrm{size}(I)/2-1$ distinct item-sizes. The algorithm outputs $(I_1,I_2)$.

It can be proven that $I_1⪯I⪯I_1+I_2$.

This algorithm runs in $O(n\lg n)$ time.

Algorithm and proof of correctness

The harmonic grouping scheme first orders the items in non-increasing order of size. It iteratively puts items into a group till the size of the group exceeds 2. Then it closes that group and opens a new group for the next pieces. Suppose $t$ such groups are created. Let $G_i$ be the $i^{\text{th}}$ group. Let $n_i$ be the number of items in $G_i$.

Let $H_1=G_1$ and $H_t=G_t$. For $i\in \{2,3,\dots ,t-1\}$, let $H_i$ be the last $n_i-n_{i-1}$ items in $G_i$ and let $G_i^{\prime }$ be the first $n_{i-1}$ items from $G_i$ with sizes raised to $max(G_i)$. Then $G_{i+1}^{\prime }⪯G_i⪯G_i^{\prime }+H_i$.

Let $I_2=\sum _{i=1}^t{H}_i$ and $I_1=\sum _{i=2}^{t-1}{G}_i^{\prime }$. $$I_1=\sum _{i=2}^{t-1}{G}_i^{\prime }⪯\sum _{i=1}^{t-2}{G}_i⪯I$$ $$I_1+I_2=G_1+\sum _{i=2}^{t-1}(G_i^{\prime }+H_i)+G_t⪰I$$ Therefore, $I_1⪯I⪯I_1+I_2$.

All items in $G_i^{\prime }$ have the same size so $I_1$ has $t-2$ distinct items. $$\mathrm{size}(I)=\sum _{i=1}^t\mathrm{size}(G_i)\ge 2(t-1)⟹t-2\le \mathrm{size}(I)/2-1$$

$$n_{t-1}\le \frac{\mathrm{size}(G_{t-1})}{min(G_{t-1})}\le \frac{3}{min(I)}$$ For $2\le i\le t-1$, $$\begin{array}{}\text{(}{H}_i\text{ has }{n}_i-n_{i-1}\text{ smallest items)}& \mathrm{size}(H_i)\le 3\frac{n_i-n_{i-1}}{n_i}\end{array}$$ $$\begin{array}{rl}\mathrm{size}(I_2)& =\sum _{i=1}^t\mathrm{size}(H_i)\\ & \le 6+3\sum _{i=2}^{t-2}\frac{n_i-n_{i-1}}{n_i}\\ \text{(harmonic bound on fraction)}& & \le 6+3\sum _{i=2}^{t-2}(H(n_i)-H(n_{i-1}))& =6+3(H(n_{t-1})-H(n_1))\\ \text{(}{n}_1\ge 2\text{)}& & \le 3H(n_{t-1})+\frac{3}{2}\text{(}H(n)\le \ln (n)+1\text{)}& & \le 3\ln (n_{t-1})+\frac{9}{2}& \le 3\ln \left(\frac{3}{min(I)}\right)+\frac{9}{2}\end{array}$$

Dependency for:

1. 1BP: Karmarkar-Karp algorithm (broken)

Info:

• Depth: 2
• Number of transitive dependencies: 7

Transitive dependencies:

1. Bin packing and Knapsack
2. Bin packing: union of input instances
3. Bin packing: predecessor of an input instance
4. Integration bound
5. Simple bound on harmonic sum
6. Harmonic bound for fraction
7. Bound on k extreme values