<p>This problem is polynomially solvable.</p>

<p><strong>Claim</strong>: 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$.</p>

<p>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]$.</p>

<p>It is easy to show that the following algorithm finds an optimal solution:</p>

<p><strong>Algorithm</strong>: 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$.</p>

<p>Thus, all that's left is to prove the claim:</p>

<p><strong>proof of claim</strong>:</p>

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

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

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

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

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

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

<p>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'&lt;j\}$, we see that sets $S_1', \ldots, S_{|X|}'$ form a partition of $\{1,2,\ldots,n\}$.</p>

<p>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.</p>

CC BY-SA 3.0
2017-06-05T21:33:31.673Z
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
CC BY-SA 3.0
2017-06-06T19:28:40.900Z
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
CC BY-SA 3.0
2017-06-07T14:15:51.757Z
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
CC BY-SA 3.0
2017-06-05T02:50:48.037Z
2017-06-05T02:50:48.037Z
Mikhail Rudoy
<p>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).</p>

<hr>

<blockquote>
  <h2>Pooling-aware bin packing</h2>
  
  <p>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$)</p>
  
  <p><strong>Simple instance:</strong>
  $$a=[0.3,0.5,0.4,0.9,0.7]\\ b=[0.6,0.3,0.6,0.1,0.2]$$</p>
  
  <p>Solution: we need 3 bins</p>
  
  <ol>
  <li>$[(0.9,0.1)]$</li>
  <li>$[(0.7,0.2),(0.5,0.3)]$</li>
  <li>$[(0.3,0.6),(0.4,0.6)]$</li>
  </ol>
</blockquote>

<hr>

<p>Note that maybe the most similar problem is the one in 
<a href="https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37147.pdf" rel="nofollow noreferrer">Michael Sindelar, Ramesh K. Sitaraman, Prashant J. Shenoy: Sharing-aware algorithms for virtual machine colocation. SPAA 2011: 367-3</a> and discussed in
<a href="https://cstheory.stackexchange.com/questions/12138/bin-packing-with-overlapping-objects">bin packing with overlapping objects</a>.</p>

<p>Thoughts / similar problems / pointers?</p>

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

<cc.complexity-theory><np-hardness><partition-problem><packing>
Is pooling-aware bin packing NP-Hard?
Paul Knight
# Is pooling-aware bin packing NP-Hard?

(Asked by: username_0 on 2017-06-04)

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](https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37147.pdf) and discussed in
[bin packing with overlapping objects](https://cstheory.stackexchange.com/questions/12138/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 :)

**Tags:** cc.complexity-theory, np-hardness, partition-problem, packing

---

## 1 answers

### Answer by username_1 on 2017-06-05. Score: 0 | Accepted answer

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'

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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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.  
> **username_0**: 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.  

---

