1
$\begingroup$

In the bin packing problem, we are given a set of items I={a1,...,an}, each item with weight w_a1,...,w_an, and a set of n bins with B={b1,..., bn} all bins with capacity C. I want to restrict the weights of the items to be polynomial in n. Is the problem still being NP-hard (restricting the weight of the items)?

Any information and sources about this would be appreciated.

Thanks.

Improve this question
$\endgroup$
1
  • $\begingroup$ The goal is to assign one item to each bin such that the number of bin needed is minimized. $\endgroup$
    – Gabb
    Feb 9, 2018 at 12:35

1 Answer 1

Reset to default
1
$\begingroup$

Assuming that you mean the usual bin packing problem, your question is answered on Wikipedia, on the page on strong NP-completeness.

A problem is strongly NP-complete exactly when it remains NP-complete even when the weights are assumed to be of polynomial size (this is not an informal definition, so this should be regarded as an informal notion). Another way to put this is that the problem remains NP-complete even when weights are encoded in unary (the two formulations might not be formally equivalent, but they are morally equivalent). Bin packing is one of the standard examples of a strongly NP-complete problem.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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