## Approximate bin-packing?

Let $$X_1,…X_n$$ denote some bins, and $$w_1,…w_m$$ some positive real numbers, where $$m \in \mathbb{N}$$, and the order matters, so e.g. we can’t switch the position of $$w_n$$ and $$w_1$$. The goal is to partition $$w_1,…w_m$$ into the bins, such that each bin contains "roughly" an equal sum of $$w_i’s$$, e.g. the sums for $$X_1,…X_n$$ could approximately equal $$100$$, so $$X_1$$ could have a sum of 104, $$X_2$$ could have a sum of 97,… etc. Let’s say this "equal sum" is $$Z$$.

Letting $$Y_i$$ be the sum for each $$i^{th}$$ bin, is there a way to choose Z such that the error is minimized, error being defined as $$\sum_i |Y_i-Z|$$, where $$1 \leq i \leq n$$?

Posted on Categories proxies

## Proof of a greedy algorithm used for a variation of bin-packing problem

we are given an array of weights W (All the wights are positive integers) and we need to put the weights inside bins. Each bin can hold a maximum of Max_val (Wi <= Max_val (0 <= i < W.size())). The variation is that the ordering of weights should not be changed (ie; Wi should be inside a bin before Wj is inserted for all i < j).

For this problem statement, intuitively we can see that a greedy approach of filling a bin till its maximum value is reached and creating a new bin for further weights will produce the minimum number of bins. I am unable to come up with a formal proof that the greedy solution is optimal. Any hints or guidelines would be great!

PS: Wi represents ith element of W array.

Posted on Categories proxies