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:

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:

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.

  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Aug 29, 2022 at 17:32
  • $\begingroup$ 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. $\endgroup$
    – xtyner
    Aug 30, 2022 at 9:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.