1
$\begingroup$

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 :)

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Paul Knight Jun 5 '17 at 21:33
  • $\begingroup$ 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. $\endgroup$ – Mikhail Rudoy Jun 6 '17 at 19:28
  • $\begingroup$ 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. $\endgroup$ – Paul Knight Jun 7 '17 at 14:15

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.