# Is pooling-aware bin packing NP-Hard?

I am unable to prove whether the following problem is NP-Hard. It seems like a bin-packing or a partition problem, without being close enough to either of them (at least I do not see the reduction to them).

## Pooling-aware bin packing

Consider 2 sets of non-negative numbers $$a=\{a_1,a_2,...,a_n\}\\b=\{b_1,b_2,...,b_n\}.$$ Which is the size of the smallest partition $P$ for the values $1$ to $n$ such that for every subset $S=\{ (a_i,b_i), (a_j,b_j),\ldots\}$ in the partition $$\max_{i\in S}a_i+\max_{j\in S}b_j\le1,\qquad \forall S\in P?$$ (I inherently assume feasibility, i.e., $a_i+b_i\le1, i=1,...,n$)

Simple instance: $$a=[0.3,0.5,0.4,0.9,0.7]\\ b=[0.6,0.3,0.6,0.1,0.2]$$

Solution: we need 3 bins

1. $[(0.9,0.1)]$
2. $[(0.7,0.2),(0.5,0.3)]$
3. $[(0.3,0.6),(0.4,0.6)]$

Note that maybe the most similar problem is the one in Michael Sindelar, Ramesh K. Sitaraman, Prashant J. Shenoy: Sharing-aware algorithms for virtual machine colocation. SPAA 2011: 367-3 and discussed in bin packing with overlapping objects.

Thoughts / similar problems / pointers?

PD: I want to apologize in advance if there is some issue with my question that I am unaware of, I am new here :)

This problem is polynomially solvable.

Claim: solving the problem on input $a = (a_1, \ldots, a_n)$ and $b = (b_1, \ldots, b_n)$ using a partition $P$ is equivalent to choosing a multiset of numbers $X$ with $|X| = |P|$ such that for $i = 1, \ldots, n$, there exists an $x \in X$ with $a_i \le x$ and $b_i \le 1-x$.

Assuming this claim, solving your problem is equivalent to finding the smallest set $X$ such that for each $i = 1, \ldots, n$, there exists an $x \in X$ with $a_i \le x$ and $b_i \le 1-x$. For any fixed $i$, this condition can be rewritten as $a_i \le x \le 1-b_i$. Thus, the problem is equivalent to finding the smallest set $X$ which includes at least one point from each interval $[a_i, 1-b_i]$.

It is easy to show that the following algorithm finds an optimal solution:

Algorithm: Initialize $X$ to be the empty set. Scan from 0 to 1. When leaving each interval during this scan, check whether the interval you are leaving already contains a point in $X$. If yes, continue without doing anything. If no, add the current value of the scan-line (i.e. the end of the interval) to $X$. Once you reach the end of the scan, output $X$.

Thus, all that's left is to prove the claim:

proof of claim:

First suppose we have a partition $P$ solving your problem. Then define $X = \{x_S~|~S \in P\}$ where $x_S = \max_{i \in S}a_i$.

If $i' \in \{1, \ldots, n\}$, then $i' \in S$ for some $S \in P$.

Since $i' \in S$, clearly we have that $a_{i'} \le max_{i \in S}a_i$. The RHS, however, is the definition of $x_S$, so this shows $a_{i'} \le x_S$.

By the conditions on the partition, $max_{i \in S}a_i + max_{i \in S}b_i \le 1$, or in other words $max_{i \in S}b_i \le 1 - max_{i \in S}a_i = 1 - x_S$. Simply applying the fact that $i' \in S$, we have that $b_{i'} \le max_{i \in S}b_i$. Putting this together, we see that $b_{i'} \le 1-x_S$.

Thus we have shown that for $i = 1, \ldots, n$, there exists an $x \in X$ with $a_i \le x$ and $b_i \le 1-x$.

Next suppose that we have a set $X$ such that for $i = 1, \ldots, n$, there exists an $x \in X$ with $a_i \le x$ and $b_i \le 1-x$.

Name the elements of $X$ as $x_1, x_2, \ldots, x_{|X|}$. Then let $S_j = \{i \in \{1,2,\ldots,n\}~|~a_i \le x_j ~\text{and}~ b_i \le 1-x_j\}$. By the property of $X$, every element of $\{1,2,\ldots,n\}$ is in at least one $S_j$. Then if we define $S_j' = \{i \in S_j~|~i \not\in S_{j'} ~\text{for}~j'<j\}$, we see that sets $S_1', \ldots, S_{|X|}'$ form a partition of $\{1,2,\ldots,n\}$.

We claim that this partition is a valid solution to your problem. Consider any part $S_j'$ in this partition. Since $S_j' \subseteq S_j$, we have that $\max_{i \in S_j'}a_i \le \max_{i \in S_j}a_i \le x_j$ and $\max_{i \in S_j'}b_i \le \max_{i \in S_j}b_i \le 1-x_j$, and so we see that $\max_{i \in S_j'}a_i + \max_{i \in S_j'}b_i \le x_j + 1-x_j = 1$. This is sufficient to show that the partition is a valid solution to your problem.

• That's beautiful solution Mr. Rudoy, thank you, you are absolutely right. I am now thinking about the extension to n vectors, "a,b,c,d,...", which was the original problem I had in mind. Do you know under which kind of problems is this problem for guidance? – Paul Knight Jun 5 '17 at 21:33
• I'm pretty sure that if you extend it to 3 vectors (a,b,c) then the problem becomes NP-hard. The 2-vector version corresponds to picking the smallest number of points on a line such that each given interval contains at least one chosen point. The 3-vector version corresponds to picking the smallest number of points in the plane such that each given horizontal-base equilateral triangle contains at least one chosen point. It's a pain, but you can reduce from X3C to show that this problem is hard. – Mikhail Rudoy Jun 6 '17 at 19:28
• Yes, I was getting the n dimensional version by extending the line 2 vectors to an n dimensional space, which regions are restricted by the conditions on the partition, pivoting in one of the vectors. I agree that the 3-vector version seems NP-Hard, reducible to exact cover 3 sets. Thanks for the help and insights. Very much appreciated. – Paul Knight Jun 7 '17 at 14:15