<p>Is the following  problem NP-complete:</p>
<p><strong>Input:</strong> A set of tuples <span class="math-container">$T = \left\{ t_i=(a_i,b_i) | 1\le i\le n \right\}$</span>, an integer <span class="math-container">$k$</span> and numbers <span class="math-container">$C,D\in \mathbb Q_{\ge 0}$</span>.</p>
<p><strong>Question:</strong> Exists a subset <span class="math-container">$S\subseteq T$</span> with <span class="math-container">$|S|\le k$</span> and
<span class="math-container">$$
\sum_{t_i\in S} a_i - C\cdot \prod_{t_i \in S} b_i \ge D.
$$</span></p>
<p>There are some related threads that did not really help me:</p>
<ul>
<li><a href="https://cstheory.stackexchange.com/questions/31215/knapsack-combining-sum-and-product">Knapsack combining sum and product</a></li>
<li><a href="https://cstheory.stackexchange.com/questions/20559/combining-subset-sum-and-subset-product-problems">Combining subset sum and subset product problems</a></li>
</ul>
<p>As the problem seems to be quite fundamental, I am quite sure that there exists a source. But I have not so many good ideas what that could be called like. I have found somewhat similar but not close enough problems:</p>
<ul>
<li>The Product Knapsack: <a href="https://link.springer.com/content/pdf/10.1007/s11590-017-1227-5.pdf" rel="nofollow noreferrer">https://link.springer.com/content/pdf/10.1007/s11590-017-1227-5.pdf</a></li>
<li>The Penalized Knapsack: <a href="https://www.sciencedirect.com/science/article/pii/S0167637705000751" rel="nofollow noreferrer">https://www.sciencedirect.com/science/article/pii/S0167637705000751</a></li>
</ul>
<p>However all relations to Knapsack result in the issue that in the presented problem there are no weights to the tuples/elements. And connections to subset-sum fail because I require <span class="math-container">$\ge D$</span>.</p>
<p>The most desirable variant for me would be <span class="math-container">$a_i\in \mathbb Q_{\ge 0}, b_i\in \mathbb Q\cap[0,1)$</span>, but I would also be happy with an idea for the case where  <span class="math-container">$a_i$</span>s and <span class="math-container">$b_i$</span>s are integers.</p>

CC BY-SA 4.0
2022-08-29T17:32:59.883Z
Let's assume $a_i\ge 0, b_i \in [0,1)$.  WLOG, we can assume $|S|=k$.  Consider these two extremes:  (1) If each $b_i$ is close to 1, then the problem might be easy: $\prod b_i \approx 1 - \sum (1-b_i)$, so the problem becomes approximately $\sum (a_i+C-Cb_i) \ge D+1$, which can be solved with a greedy algorithm. (2) If each $b_i$ is far from 1, the problem also might be easy: $\prod b_i$ is exponentially small (in $k$), so the problem is approximately $\sum a_i \ge D$, which can also be solved with a greedy algorithm.  Any ideas for how to handle intermediate cases?
D.W.
CC BY-SA 4.0
2022-08-30T09:31:07.243Z
The idea is actually quite interesting. Indeed when the $b_i$s are relatively close to each other (informally) then we can approximate
$$
\prod_{t_i\in S} b_i \approx b_1^{|S|}.
$$
And from that point we can go greedy about the $a_i$s. That generalizes the idea for "intermediate cases". So the the question is what about $b_i$s having quite values that are not so close to each other.
xtyner
<np-hardness><reductions>
Complexity of a sum with a product
xtyner
# Complexity of a sum with a product

(Asked by: username_0 on 2022-08-29)

Is the following problem NP-complete:

**Input:** A set of tuples $T = \left\{ t\_i=(a\_i,b\_i) | 1\le i\le n \right\}$, an integer $k$ and numbers $C,D\in \mathbb Q\_{\ge 0}$.

**Question:** Exists a subset $S\subseteq T$ with $|S|\le k$ and
$$
\sum\_{t\_i\in S} a\_i - C\cdot \prod\_{t\_i \in S} b\_i \ge D.
$$

There are some related threads that did not really help me:

* [Knapsack combining sum and product](https://cstheory.stackexchange.com/questions/31215/knapsack-combining-sum-and-product)
* [Combining subset sum and subset product problems](https://cstheory.stackexchange.com/questions/20559/combining-subset-sum-and-subset-product-problems)

As the problem seems to be quite fundamental, I am quite sure that there exists a source. But I have not so many good ideas what that could be called like. I have found somewhat similar but not close enough problems:

* The Product Knapsack: <https://link.springer.com/content/pdf/10.1007/s11590-017-1227-5.pdf>
* The Penalized Knapsack: <https://www.sciencedirect.com/science/article/pii/S0167637705000751>

However all relations to Knapsack result in the issue that in the presented problem there are no weights to the tuples/elements. And connections to subset-sum fail because I require $\ge D$.

The most desirable variant for me would be $a\_i\in \mathbb Q\_{\ge 0}, b\_i\in \mathbb Q\cap[0,1)$, but I would also be happy with an idea for the case where $a\_i$s and $b\_i$s are integers.

**Tags:** np-hardness, reductions

> **Comments:**
> **username_1**: Let's assume $a_i\ge 0, b_i \in [0,1)$.  WLOG, we can assume $|S|=k$.  Consider these two extremes:  (1) If each $b_i$ is close to 1, then the problem might be easy: $\prod b_i \approx 1 - \sum (1-b_i)$, so the problem becomes approximately $\sum (a_i+C-Cb_i) \ge D+1$, which can be solved with a greedy algorithm. (2) If each $b_i$ is far from 1, the problem also might be easy: $\prod b_i$ is exponentially small (in $k$), so the problem is approximately $\sum a_i \ge D$, which can also be solved with a greedy algorithm.  Any ideas for how to handle intermediate cases?  
> **username_0**: The idea is actually quite interesting. Indeed when the $b_i$s are relatively close to each other (informally) then we can approximate $$ \prod_{t_i\in S} b_i \approx b_1^{|S|}. $$ And from that point we can go greedy about the $a_i$s. That generalizes the idea for "intermediate cases". So the the question is what about $b_i$s having quite values that are not so close to each other.  

---

## 0 answers

