1
$\begingroup$

Is the following problem polynomial ? Or NP-Complete ?

Problem: Bin packing with 2 types of objects.

Input: $C$, the capacity of each bin, $N_a, N_b$ the numbers of objects $a$ and $b$, $w_a,w_b$ the weight of the objects, $k$, the maximum number of bins.

Output: Yes if all objects fit in the $k$ bins without exceeding the capacity of any bin or cutting objects, No otherwise

My first intuition was that with only two types of objects, there must be less solution and maybe enumeration is polynomial, so I tried count them.

For an instance of size $n$ (with $n$ objects), we can encode solutions as $n$-tuples $[0,1,1...,0,1]$ (the first objects being in the first bin until it's full, then the second, etc). For instances of size $n$, there are $2^n$ distinct solutions. Since there are $n$ instances of size $n$ (I mean, $n$ pairs $(N_a,N_b)$ such that $N_a+N_b=n$), and by the pigeonhole principle, there must be an instance with at least $2^n/n$ solutions. So a simple enumeration of solutions doesn't work.

Then, I started thinking that the problem may be NP-Complete. Reducing a graph problem seems no to be a good idea: graphs are big structures, and this problem as only a few numbers as an input. At this point, I realized that all the NP-Complete problems I've heard of had biggers inputs.

Now, I'm a bit confused. I can't figure out a good algorithm or a reduction.

$\endgroup$
1
$\begingroup$

The problem can be solved in polynomial time. See A Polynomial Algorithm for Multiprocessor Scheduling with Two Job Lengths, An Asymptotically Exact Algorithm for the High Multiplicity Bin Packing Problem, or On the bin packing problem with a fixed number of object weights.

$\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.