Is this problem NP-Complete (Bin packing with seperable items and penalty)?

Question

The problem is a bit like bin-packing, so I'll describe it with similar naming:

• You have $N$ bins, with the same size, $V$, where $V$ is a positive integer

• This problem has items, and also "pieces" of items: each item is considered a piece, and each piece must always have a "valid size": size must be a positive integer

• You have a set, $S_1$, of items that must all be placed into bins, but can be seperated into "pieces" of any valid sizes (ie. the sum of the sizes of the pieces of an item must always equal the original size of the item)

• You have a second set, $S_2$, with non-seperable items of all the same size, $F$, where the cardinality of this set is sufficiently large / unbounded

• If you place any piece from $S_1$ into a bin you must also place exactly one item from $S_2$ into the same bin

Given an instance is it possible to place all elements from $S_1$ into the bins without exceeding the capacity of the bins?

More simply put: Is bin-packing still NP-Complete if you allow for items to be separated into pieces, but there is a "penalty" for having more pieces in each bin, where you're forced to place a "filler" between each piece in a bin?

I've considered trying to reduce from bin-packing, scheduling, 3-partition, 3-col, 3-SAT, TSP, but I can't think of a way to do it. Also, in trying to solve the problem in poly time. I can only think of approximation algorithms such as greedily placing the largest item in the bin with the largest remaining capacity.

Any answers or observations on this would be very appreciated.

Answer 1

We can reduce from 3-Partition. In 3-Partition instance we have:

• A set, $S = \{ s_1, s_2, ..., s_n \}, n = 3m$, where $m$ in a positive integer

• $B = \sum_{ i = 1 }^{ n } \frac { s_i } { 3 }$

• $\frac { B } { 4 } < s_k < \frac { B } { 2 }$, $\forall k \in \{ 1, ..., n \}$

Where the problem is whether $S$ be partitioned into m triples such that they all have the same sum, $B$.

To reduce from my problem, let:

• $N = m$
• $F$ may be set to anything
• $V = B + 3F$
• $S_1 = S$, ie. the values from the 3-Partition instance become the item sizes in the new problem

In the reduced problem the total space available is:

size of each bin $\times$ number of bins

$ = (B + 3F) m $

$ = Bm + 3mF $ (1)

And the total space that the items will occupy is at least:

Sum of item sizes from $S_1 +$ number of pieces, $p$, from items $S_1 \times$ size of items in $S_2$

$ = Bm + pF $ (2)

We know that:

$ p \geq n = 3m $ (3)

and

total space occupied $\leq$ total space available:

(1),(2) $\Rightarrow Bm + pF \leq Bm + 3mF $

$\Rightarrow p \leq 3m $

(3) $\Rightarrow p = 3m $

Implies that for the reduced problem to be satisfiable then all the available bin space is occupied by the items, and that it's not possible to separate any of the items from $S_1$ into smaller pieces. (4)

It's clear now that this is equivalent to the 3-partition problem, but I've shown it below:

If a 3-partition problem is satisfiable then there exists corresponding triplets in the reduced problem that can be placed into each of the separate bins with exactly $3F$ remaining in each to allow for the required items from $S_2$. Hence 3-partition $\Rightarrow$ reduced problem. (5)

Because $\frac {B}{4} < s_k$ from the original 3-particiation problem, and item sizes in $S_1$ correspond to the values in $S$ (from 3-partition), we know that if we place more than 3 items in a bin that we exceed the capacity of the bin:

$s_{1,k} > \frac {B}{4}$

If we place $x$ items into a bin, where $s_{min}$ is the size of the smallest item:

total size of bin used for $x$ items $ = x ( s_{min} + F )$ (6)

Because $\frac {B}{4} < s_k$ from the original 3-particiation problem, and item sizes in $S_1$ correspond to the values in $S$ (from 3-partition):

$ s_{min} > \frac {B}{4} $ (7)

(5), (6) $ \Rightarrow$ total size of bin used for $x$ items $ > x ( \frac {B}{4} + F )$

$\Rightarrow$ total size of bin used for $x$ items $>$ total capacity of bins $ = B + 3F $, $ \forall x > 3 $

$\Rightarrow$ A satisfiable solution to the reduced problem has no more than 3 items in any bin. (8)

Likewise, because $s_k < \frac {B}{2}$ from the original 3-particiation problem:

$ s_{max} < \frac {B}{2} $

$ \Rightarrow$ total size of bin used for $x$ items $ < x ( \frac {B}{2} + F )$

$\Rightarrow$ total size of bin used for $x$ items $<$ total capacity of bins $ = B + 3F $, $ \forall x < 3 $

(4) $\Rightarrow$ A satisfiable solution to the reduced problem has no fewer than 3 items in any bin. (9)

(8), (9) $\Rightarrow$ A satisfiable solution to the reduced problem has exactly 3 items in each bin. (10)

If any reduced problem is satisfiable: We know from (4) that the items cannot be separated; we know from (10) that each bin contains exactly 3 items.

$\Rightarrow$ The triples from each bin (items from $S_1$) have sizes that sum to $B$, and that the sizes for each item in $S_1$ have a one-to-one correspondence to the values in the set $S$. Therefore there is a partition of the $S$ set into triples, where each of the triples sums to $B$. Hence reduced problem $\Rightarrow$ corresponding 3-partition problem. (11)

So long as we accept that the problem from the question is in NP (I'm not going to prove this!) (5), (11) $\Rightarrow$ the problem from the question is in NP-Complete.