Bin packing when items can be broken

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?

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

StackExchange Computer Science Q#135598, answer score: 4