patternMinor
Can this special case of bin packing be solved in polynomial time?
Viewed 0 times
thiscasecanbinpolynomialpackingtimespecialsolved
Problem
Consider a multiset of $n$ integers, where each integer is between $1$ and $3 M$. The sum of all integers is $3 S$. There are three bins. The capacity of each bin is $C = S + M$.
Is there a polynomial-time algorithm to decide whether all integers can be packed into the bins?
To explain why this specific case is special, consider some variants of the problem:
Since $x \leq 3 M$, this sum is larger than $3 S + 2 x - 3 x = 3 S - x$. But then the sum of all integers plus $x$ is larger than $3 S$ - a contradiction.
The case $C = S+M$ is between these extremes: it is larger than $S$ for which the problem is hard, but smaller than $S+2M$ for which the answer is always yes.
Is this case is easy or hard?
Is there a polynomial-time algorithm to decide whether all integers can be packed into the bins?
To explain why this specific case is special, consider some variants of the problem:
- When $C$ is not fixed, the problem is NP-hard, since it is a special case of the bin-packing problem.
- When $C = S$, the problem is NP-hard, since it is equivalent to 3-way number partitioning.
- When $C \geq S + 2 M$, the problem is easy since the answer is always "yes". Proof: put the items in an arbitrary order into the bins as long as there is room. Suppose by contradiction that not all integers are packed; let $x$ be some remaining integer. Then the sum in each bin is larger than $C-x$, so the sum in all bins is more than $3 C - 3 x \geq 3 S + 6 M - 3 x$.
Since $x \leq 3 M$, this sum is larger than $3 S + 2 x - 3 x = 3 S - x$. But then the sum of all integers plus $x$ is larger than $3 S$ - a contradiction.
The case $C = S+M$ is between these extremes: it is larger than $S$ for which the problem is hard, but smaller than $S+2M$ for which the answer is always yes.
Is this case is easy or hard?
Solution
Yes, there is a polynomial time solution. It is not very pretty, so simplifications or alternative approaches are welcome.
TL;DR: the exact weights are rarely important, so we can round them up to a multiple of $K := \lceil \frac{3M}{n^3} \rceil$ or something similar (there are only $\approx n^3$ rounded item weights). Then, we can do dynamic programming that keeps track of rounded weights for two bins and exact weight for the third bin. If we somehow got a false negative result, then in all solutions two bins are almost full at the same time. Such cases turn out to be highly structured (all items have weights that are either close to $0$ or close to $3M$, the total weight of the former is small and there are exactly $3\ell + 2$ items of the latter type for some $\ell$) and can be solved by an algorithm that greedily moves items between bins.
Only the case when $M > n^4$ is interesting, otherwise simple dynamic programming will do the job. Similarly, assume that $n > 10^9$ to make things like $Kn^2$ negligible when compared to $M$. Do not worry, actual precise bounds are much better, I just chose these to not think about the details too much.
As mentioned above, the first step is to try finding a solution with "discretised" weights. Pick $K := \lceil \frac{3M}{n^3} \rceil$. For each item, its discrete weight is its weight rounded up to a multiple of $K$. For each bin, its discrete size is its size, rounded down to a nearest multiple of $K$. Items discretely fit into a bin, if the sum of their discrete weights does not exceed the discrete size of the bin. Clearly, if items discretely fit into a bin, then they do fit in the bin for real. The opposite implication is not true, but only because of rounding issues; if several items fit into a bin, but not discretely, then their total weight is at least $(S + M) - (n+1)K$ (at most $n$ items, each causes a rounding error of at most $K$; rounding of the bin size also causes a rounding error of at most $K$). Let us say that any bin with sum of weights at least $(S + M) - (n+1)K$ is almost full. Unless the bin is almost full, discrete fitting and real fitting is the same thing.
Consider any solution (by solution, I mean a correct distribution of items to bins). There can be at most two almost full bins; otherwise the total weight of items is at least $3(S + M) - 3(n+1)K = 3S + (3M - 3(n+1)K) > 3S$, as $K \approx \frac{3M}{n^3}$).
We can find all solutions with at most one full bin by simple dynamic programming, which answers the following question: suppose that we distributed some prefix of items to bins and we know the sums of discrete item weights in the second and the third bins (there are only $n \cdot \lceil \frac{3M}{K} \rceil \approx n^4$ possible discrete weights for each bin), what is the minimal possible total real weight of items in the first bin in this case? We will not miss out the solutions where there is at most one almost full bin (because we can track the weight in one bin precisely).
The only remaining problem is the case when all optimal solutions have exactly two almost full bins. Let us study the structure of the solutions in this case (this is not an algorithmic part, but rather only a mathematical setup; so, we are not interested in algorithmic aspects for the following few paragraphs).
Suppose that the first bin is filled up to $S + M - \varepsilon_1$ and the second is filled up to $S + M - \varepsilon_2$, where $\max(\varepsilon_1, \varepsilon_2) \leqslant (n+1)K$. Then, the third bin is filled up to $3S - (S + M - \varepsilon_1) + (S + M - \varepsilon_2) = S - 2M + \varepsilon_1 + \varepsilon_2$.
Let us try to move some items from the first bin to the third (in order to make them both not almost full). Why cannot we do that? Because all items in the first bin are either small (have weight at most $(n+1)K$) and the first bin will not stop being almost full, or because all items in the first bin are big (have weight at least $3M - 3K(n+1)$), so the third bin will become almost full (or, maybe, there is not even enough space for the item). About the latter part: if the weight of an item is less than $3M - 3K(n+1)$, then the third bin will be filled up to less than
\begin{equation*}
S - 2M + \varepsilon_1 + \varepsilon_2 + (3M - 3K(n+1)) = S + M - (3K(n+1) - \varepsilon_1 - \varepsilon_2) \leqslant S + M - K(n+1),
\end{equation*}
because $\max(\varepsilon_1, \varepsilon_2) \leqslant K(n+1)$.
Now, let us move all small items from the first bin to the third bin one-by-one. Then, either the first one stops being almost full at some point (while the third one is still not almost full, it still had almost $3M$ space left before all operations), or we move them all. Similarly, move all small items from the second bin to the third bin.
Now, all items in the first and the second bins are big, but they are still almost full. As before, denote the space left in the first and the second bins by $\varepsilon_1$ and $\varepsilon_2$. I claim that no
TL;DR: the exact weights are rarely important, so we can round them up to a multiple of $K := \lceil \frac{3M}{n^3} \rceil$ or something similar (there are only $\approx n^3$ rounded item weights). Then, we can do dynamic programming that keeps track of rounded weights for two bins and exact weight for the third bin. If we somehow got a false negative result, then in all solutions two bins are almost full at the same time. Such cases turn out to be highly structured (all items have weights that are either close to $0$ or close to $3M$, the total weight of the former is small and there are exactly $3\ell + 2$ items of the latter type for some $\ell$) and can be solved by an algorithm that greedily moves items between bins.
Only the case when $M > n^4$ is interesting, otherwise simple dynamic programming will do the job. Similarly, assume that $n > 10^9$ to make things like $Kn^2$ negligible when compared to $M$. Do not worry, actual precise bounds are much better, I just chose these to not think about the details too much.
As mentioned above, the first step is to try finding a solution with "discretised" weights. Pick $K := \lceil \frac{3M}{n^3} \rceil$. For each item, its discrete weight is its weight rounded up to a multiple of $K$. For each bin, its discrete size is its size, rounded down to a nearest multiple of $K$. Items discretely fit into a bin, if the sum of their discrete weights does not exceed the discrete size of the bin. Clearly, if items discretely fit into a bin, then they do fit in the bin for real. The opposite implication is not true, but only because of rounding issues; if several items fit into a bin, but not discretely, then their total weight is at least $(S + M) - (n+1)K$ (at most $n$ items, each causes a rounding error of at most $K$; rounding of the bin size also causes a rounding error of at most $K$). Let us say that any bin with sum of weights at least $(S + M) - (n+1)K$ is almost full. Unless the bin is almost full, discrete fitting and real fitting is the same thing.
Consider any solution (by solution, I mean a correct distribution of items to bins). There can be at most two almost full bins; otherwise the total weight of items is at least $3(S + M) - 3(n+1)K = 3S + (3M - 3(n+1)K) > 3S$, as $K \approx \frac{3M}{n^3}$).
We can find all solutions with at most one full bin by simple dynamic programming, which answers the following question: suppose that we distributed some prefix of items to bins and we know the sums of discrete item weights in the second and the third bins (there are only $n \cdot \lceil \frac{3M}{K} \rceil \approx n^4$ possible discrete weights for each bin), what is the minimal possible total real weight of items in the first bin in this case? We will not miss out the solutions where there is at most one almost full bin (because we can track the weight in one bin precisely).
The only remaining problem is the case when all optimal solutions have exactly two almost full bins. Let us study the structure of the solutions in this case (this is not an algorithmic part, but rather only a mathematical setup; so, we are not interested in algorithmic aspects for the following few paragraphs).
Suppose that the first bin is filled up to $S + M - \varepsilon_1$ and the second is filled up to $S + M - \varepsilon_2$, where $\max(\varepsilon_1, \varepsilon_2) \leqslant (n+1)K$. Then, the third bin is filled up to $3S - (S + M - \varepsilon_1) + (S + M - \varepsilon_2) = S - 2M + \varepsilon_1 + \varepsilon_2$.
Let us try to move some items from the first bin to the third (in order to make them both not almost full). Why cannot we do that? Because all items in the first bin are either small (have weight at most $(n+1)K$) and the first bin will not stop being almost full, or because all items in the first bin are big (have weight at least $3M - 3K(n+1)$), so the third bin will become almost full (or, maybe, there is not even enough space for the item). About the latter part: if the weight of an item is less than $3M - 3K(n+1)$, then the third bin will be filled up to less than
\begin{equation*}
S - 2M + \varepsilon_1 + \varepsilon_2 + (3M - 3K(n+1)) = S + M - (3K(n+1) - \varepsilon_1 - \varepsilon_2) \leqslant S + M - K(n+1),
\end{equation*}
because $\max(\varepsilon_1, \varepsilon_2) \leqslant K(n+1)$.
Now, let us move all small items from the first bin to the third bin one-by-one. Then, either the first one stops being almost full at some point (while the third one is still not almost full, it still had almost $3M$ space left before all operations), or we move them all. Similarly, move all small items from the second bin to the third bin.
Now, all items in the first and the second bins are big, but they are still almost full. As before, denote the space left in the first and the second bins by $\varepsilon_1$ and $\varepsilon_2$. I claim that no
Context
StackExchange Computer Science Q#141252, answer score: 2
Revisions (0)
No revisions yet.