How do I select a subset such that the sum and the product are greater than some value?

Question

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.

Answer 1

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.