3
$\begingroup$

Wikipedia claims that bin packing is strongly NP-complete. Unfortunately I haven't been able to find a proof. Does anyone know where to find it?

$\endgroup$
5
$\begingroup$

Such a proof is outlined in Garey and Johnson, 'Strong' NP-Completeness Results: Motivation, Examples, and Implications, mentioned in the Wikipedia article. The proof is by a straightforward reduction from 3-PARTITION. The problem 3-PARTITION one is given $3n$ numbers, and the task is to decide whether they can be split into triples of equal sum. There is a straightforward reduction from 3-PARTITION to BIN-PACKING: if the sum of the numbers is $nB$, ask whether the $3n$ numbers can be packed into $n$ bins of size $B$.

The strong NP-completeness of 3-PARTITION was proved in a different paper of Garey and Johnson, Complexity results for multiprocessor scheduling under resource constraints. The proof is quite long, ultimately a reduction from 3DM (3-dimensional matching), but going through many intermediate steps.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.