1
$\begingroup$

I have asked few days ago this question. Now I am simplifying the problem a little bit.

Given two sets $A=\{a_1,\ldots,a_n\}$, and $B=\{b_1,\ldots,b_n\}$ of non-negative integers, a positive integer $k<n$ and a positive integer $\Delta$. The question is: is there a subset of $S$ of $\{1,\ldots,n\}$ of size $|S|\leq k$ such that $$\left(1+\sum_{i\in S}a_i\right)\left(1+\sum_{i\in S}b_i\right)\geq\Delta$$ Say no, if no such subset exists. Note.$ \Delta$ is greater than $1$ and not big enough.

My question is:

  • How do I solve this problem? I do not know if this is an NP-complete problem or not. Do you see some hardness or reduction?

My attempt: First I failed to to prove that it is a hard problem. I tried to reduce from PARTITION but no way. I give up and I tried to design an algorithm. Here is my algorithm.

  1. Choose $S=\emptyset$ and $P=0$
  2. Choose the $i$ of the largest sum $a_i+b_i$ and add it to $S$
  3. Let $j$ go from $1$ to $n$ except $i$ do
    • 3.1. Add $j$ to $S$
    • 3.2. Calculate the product above with $S=\{i,j\}$ and store it in $P$
  4. Pick the $j$ with the highest $P$
  5. Re-do this $k$ times.

In this algorithm optimal?

Note: The real question is about the hardness of the problem. Thanks.

$\endgroup$
  • 1
    $\begingroup$ See if this answer helps: cs.stackexchange.com/a/52658/683. $\endgroup$ – Yuval Filmus Feb 19 '16 at 5:29
  • 2
    $\begingroup$ Have you tried running your algorithm on a few instances? It might be easy to find a counterexample if your algorithm indeed doesn't work. $\endgroup$ – Yuval Filmus Feb 19 '16 at 5:30
  • 1
    $\begingroup$ Have you tried greedy algorithms? There are probably only a few reasonable strategies, and each one can be quickly tested by running each one on a few instances to look for counterexamples. (Also, note that there's a pseudopolynomial time algorithm, using dynamic programming.) $\endgroup$ – D.W. Feb 19 '16 at 6:36
  • $\begingroup$ This problem is very close to asking whether you can make $$\left(\sum_{i \in S} a_i \right) \left(\sum_{i \in S} b_i \right) \ge \Delta.$$ I don't know if it's any easier to think about that variant of the problem. $\endgroup$ – D.W. Feb 19 '16 at 6:40
  • $\begingroup$ Have you tried proving your algorithm correct/optimal? $\endgroup$ – Raphael Feb 20 '16 at 1:20
3
$\begingroup$

Thanks to Yuval for the link. I think I can prove now that the problem, called PRODUCT, is NP-hard by a reduction from EQUAL-PARTITION, the variant of PARTITION in which we require both parts to have equal sizes.

Given an instance $\{x_1,\ldots,x_n\}$ of EQUAL-PARTITION (with $x_i > 0$ and $n$ is even), consider an instance of my problem with $k = n/2$, $\Delta=\left(1+nM/2+A/2\right)^2$ for large enough $M$ (i.e., $M = \max_i x_i$ ) and $A=\sum_{i}x_i$ , and let $a_i=M+x_i$ for all $i$ and $b_i=M+2A/n-x_i$ for all $i$.

This is a polynomial time reduction.

Now let us prove that EQUAL-PARTITION is solved $\iff$ PRODUCT is solved.

  • "$\Rightarrow$" Suppose that EQUAL-PARTITION is solved. Then there exists $S$ of size $|S|=n/2$ such that $$ \sum_{i\in S}x_i=\sum_{i\in S'}x_i=A/2, $$ where $S\cup S'=\{1,\ldots,n\}$ and $S\cap S'=\emptyset$ and $|S|=|S'|=n/2$. Now take the solution to PRODUCT to be $S$. We have \begin{align} &\left(1+\sum_{i\in S}a_i\right)\left(1+\sum_{i\in S}b_i\right)\geq\Delta\\ \iff&\left(1+\sum_{i\in S}(M+x_i)\right)\left(1+\sum_{i\in S}(M+2A/n-x_i)\right)\geq\Delta\\ \iff&\left(1+nM/2+\sum_{i\in S}x_i\right)\left(1+nM/2+A-\sum_{i\in S}x_i\right)\geq\Delta\\ \iff&\left(1+nM/2+A/2\right)\left(1+nM/2+A/2\right)=\left(1+nM/2+A/2\right)^2\\ \end{align}
  • "$\Leftarrow$" Suppose that PRODUCT is solved. Then there exists $S$ of size $|S|=n/2$ such that \begin{align} \require{overset} &\left(1+\sum_{i\in S}a_i\right)\left(1+\sum_{i\in S}b_i\right)\geq\Delta\\ \iff&\left(1+\sum_{i\in S}(M+x_i)\right)\left(1+\sum_{i\in S}(M+2A/n-x_i)\right)\geq\Delta\\ \iff&\left(1+nM/2+\sum_{i\in S}x_i\right)\left(1+nM/2+A-\sum_{i\in S}x_i\right)\geq\Delta\\ \iff&\left(\alpha+\sum_{i\in S}x_i\right)\left(\alpha+A-\sum_{i\in S}x_i\right)\geq\Delta\\ \iff&\alpha^2+\alpha A+A\sum_{i\in S}x_i-\left(\sum_{i\in S}x_i\right)^2\geq\Delta\\ \iff&\left(\sum_{i\in S}x_i\right)^2-A\sum_{i\in S}x_i+\Delta-\alpha^2-\alpha A\leq 0\\ \iff&X^2-AX+\Delta-\alpha^2-\alpha A\leq 0\\ \overset{(a)}{\iff}&X^2-AX+\Delta-\alpha^2-\alpha A= 0\\ \iff&X= A/2\\ \end{align}

Finally, PRODUCT is NP-hard.

$\endgroup$
  • 1
    $\begingroup$ One subtlety: your $b_i$ might be not integers. $\endgroup$ – Denis Pankratov Feb 19 '16 at 23:53
  • $\begingroup$ You are right but I think that issue can be fixed. $\endgroup$ – 1-approximation Feb 20 '16 at 0:37

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.