4
$\begingroup$

In the bin packing problem, there are some $m$ items of size less than $1$, and they have to be packed into as few as possible bins of size $1$. The problem is NP-hard, but if we are allowed to break some items then it becomes easy, since each bin can be filled completely.

What if we are allowed to break (to as many pieces as we like) only $k$ items of our choice, where $k$ is a fixed constant - is the problem still NP-hard?

$\endgroup$
4
  • $\begingroup$ Can one item be broken into more than two parts? $\endgroup$ – xskxzr Feb 17 at 11:30
  • $\begingroup$ @xskxzr yes, two or more parts. $\endgroup$ – Erel Segal-Halevi Feb 17 at 11:32
  • $\begingroup$ Your problem is a generalization of bin-packing, so it cannot be easier (bin-packing corresponds to the case $k=0$). $\endgroup$ – Steven Feb 17 at 12:09
  • $\begingroup$ $k$ is not part of the input - it is a fixed parameter. For $k=0$ the problem is NP-hard, but maybe for $k=1$ it is easier? $\endgroup$ – Erel Segal-Halevi Feb 17 at 12:09
3
$\begingroup$

Here is a proof that the problem remains hard when $k=1$. For simplicity it uses an item of size equal to the bin capacity. If you require each item to be smaller than the bin capacity you can subtract a small enough constant from this item's size.

Consider an instance of $3$-partition in which $3n$ positive integers $x_1, x_2, \dots, x_{3n}$ of total sum $S$ need to be partitioned into $n$ triples $t_1, \dots, t_n$, each with total sum at most $T=\frac{S}{n}$, where $T$ is also an integer.

Assume that $x_i \ge \frac{2T}{7}$ (it is known that the problem remains strongly NP-complete in this case). Furthermore assume that $n > \max\{8,T+1\}$ (if this is not the case, multiply each integer in the instance by $10$, add many copies of the integers in $\{10T-2, 1, 1\}$ to the input, and then convert the resulting instance into an instance that satisfies $x_i \ge \frac{2T}{7}$. This conversion multiplies the new value of $T$ by $7$).

Consider the instance of your version of bin-packing in which $k=1$ and you need to pack the set of elements $Y = \{y_1, \dots, y_m\}$ into the fewest number of bins of capacity $n T$ (you can set the capacity of each bin to $1$ by a suitable scaling of all the involved quantities). Let $m=3n+1$, $y_m = nT$ and $y_i = (n-1) x_i$ for $i=1,\dots,3n$.

If the $3$-partition instance is a yes-instance then $Y$ can be packed into $n$ bins.

Create a bin $b = (y_i, y_j, y_h)$ for each triple $t = (x_i, x_j, x_h)$ of a solution of $3$-partition. Notice that $y_i + y_j + y_h = (n-1) (x_i + x_j +x_h) = (n-1)T$, leaving $b$ with unused capacity of $T$. The only element not assigned to a bin is $y_m$. Split $y_m = nT$ into $n$ pieces of size $T$ each, and add a piece to each of the $n$ bins.

If $Y$ can be packed into $n$ bins then the $3$-partition instance is a yes-instance.

Notice that $\sum_{i=1}^m y_i = (n-1) \sum_{i=1}^{3n}x_i + nT = (n-1)nT + nt = n \cdot nT$, showing that each each of the $n$ bins must be completely full.

We can assume w.l.o.g., that if some element is split into pieces, this element is $y_m$. Indeed, if an element $y' \neq y_m$ is split, there must be one bin $b'$ that is used entirely for $y_m$. We can then swap each piece of $y'$ with a piece of $y_m$, so that $y'$ is now entirely contained in $b'$.

Notice now that each bin $b$ must contain exactly $3$ elements from $\{ y_1, \dots, y_{3n}\}$. Indeed, if this was not true there would exist a bin that contains at least $4$ elements from $\{ y_1, \dots, y_{3n}\}$ and its used capacity would be at least $$ 4(n-1)\left(\frac{2T}{7}\right) = \left( \frac{8}{7}n - \frac{8}{7} \right)T > nT. $$

We construct a solution for the $3$-partition instance by creating a triple $t = (x_i, x_j, x_h)$ for each bin $b$ containing $y_i, y_j, y_h$ with $i,j,h \le 3n$. The total weight of $t$ is at most: $$ x_i + x_j + x_h = \frac{y_i + y_j + y_h}{n-1} \le \frac{nT}{n-1} = \frac{(n-1)T+T}{n-1} = T + \frac{T}{n-1} < T+1, $$ i.e., $x_i + x_j + x_h \le T$.

$\endgroup$
3
  • $\begingroup$ (a) $T = 3S/n$ -- should this be $T = S/n$? (b) "Add many copies of integers to the input" -- this requires the assumption that $T$ is polynomial in $n$ (which is fine, since 3-partition is strongly NP-hard). (c) I am not sure about the two initial reductions - adding many integers to make $n>T+1$, and converting the instance such that every integer is at least $2 T /7$. The problem is that the second conversion changes $T$, which harms the first condition, and the first conversion harms the second condition. $\endgroup$ – Erel Segal-Halevi Feb 18 at 20:37
  • $\begingroup$ (a) yes, sorry. (b) that's correct. This is why I remark the problem is remains strongly NP-complete. (c) The second conversion only multiplies $T$ by a factor of $7$, and the procedure that allows you to add the integers only multiplies it by $10$ (regardless of how many integers are added). Let $T' = 70T$. Add many integers... roughly $10 \cdot 7 \cdot T + 1 = 70 T + 1 \ge T' + 1 \in \text{poly}(n)$. $\endgroup$ – Steven Feb 18 at 21:05
  • $\begingroup$ I see. Thanks! It is interesting what happens when the number of bins is fixed, e.g. 3 bins - this is probably a topic for a different question. $\endgroup$ – Erel Segal-Halevi Feb 20 at 20:14

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.