Bin packing approximation algorithm

974 Views Asked by At

I know that bin packing cannot be solved in $\mathrm P$ unless $\mathrm P=\mathrm{NP}$, because we could solve partition problem.

However, I do not see why this theorem is a collorary.

There is no ρ-approximation algorithm with $ 2\rho < 3 $ for Bin Packing unless $ \mathrm P = \mathrm{NP} $.

1

There are 1 best solutions below

1
On BEST ANSWER

Usually, you reduce the partition problem to the bin packing problem as follows: Let an instance of the partition problem be given by integers $a_1, \ldots, a_n$. Define an instance of the bin packing problem by integers $a_1, \ldots, a_n$ and bin size $\frac{1}{2} \sum_{i = 1}^n a_i$. Then the partition problem has a solution if and only if the bin packing instance uses exactly two bins.

The non-existance of an $\rho$-approximation with $2 \rho < 3$ follows from this proof by the following observation: If such an approximation would exist, then this approximation would solve every bin packing instance which corresponds to an instance of the partition problem which admits a solution. Thus, such an approximation could be used to decide whether an instance of the partition problem has a solution or not.