2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ And thanks for making me think about 3-partition again. I can’t see how to solve it with 3 bins in the reduction, but I see another way! I’ll upload it here once I’ve formalised it. Thank you for your help!! $\endgroup$ – Elliott - Reinstate Monica Mar 27 at 17:35
  • $\begingroup$ The 3-bin approach was for when I thought that placing a piece from S_1 meant that you had to place a piece from S_2 in some bin, not necessarily the same bin. Anyway I'm glad you found it useful :) $\endgroup$ – j_random_hacker Mar 27 at 17:40
  • 1
    $\begingroup$ If you has figured out this problem, please write an answer (yes, you can answer your own question) $\endgroup$ – xskxzr Mar 28 at 8:54
  • $\begingroup$ Okay, thanks. I've done so. I re-labled a couple of things in the question to make the syntax of my answer slightly easier. I probably proved a little too formally as well... $\endgroup$ – Elliott - Reinstate Monica Mar 28 at 15:55
0
$\begingroup$

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.

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