<p>I think both of your problems are in P.  Here's an algorithm that works in P without any restriction on the $(a_i,b_i)$ pairs.</p>

<p>Formulate your problem as the problem of choosing $x\in\{0,1\}^n$ subject to $\sum_i x_i = k$ so as to maximize
$$\textstyle f(x) = \pi(x) + \sum_i x_i a_i$$
where $\pi(x)=\prod_i \exp( x_i \beta_i)$ and $\beta_i = \ln b_i$.  Relax the problem to allow $x\in[0,1]^n$. </p>

<p>For intuition, note that the function $f(x)$ is convex, so it is maximized over $x\in[0,1]^n$ at some $x\in\{0,1\}^n$. (To see the latter, note that any $x\in [0,1]^n$ with $\sum_i x_i = k$ is the weighted average of integer points $x'$ in $\{0,1\}^n$ with $\sum_i x'_i = k$, and $f(x)$ is at most the corresponding weighted average of $f(x')$ over those integer points, so one of those integer points $x'$ has $f(x') \ge f(x)$.)</p>

<p>Anyhow, find an optimal integer solution $x$ in polynomial time as follows.
The first derivative of $f$ with respect to $x_i$ is
$$\textstyle a_i + b_i\, \pi(x),$$
so (given the constraint $\sum_i x_i = k$), there exists $\lambda$ such that for the optimal $x\in[0,1]^n$,
$$x_i = \begin{cases}
0 &amp; \text{ if } a_i + b_i \pi(x) &lt; \lambda \\
1 &amp; \text{ if } a_i + b_i \pi(x) &gt; \lambda \\
? &amp; \text{ if } a_i + b_i \pi(x) = \lambda.
\end{cases}$$</p>

<p>Furthermore, WLOG there are at most two indices $i$ that are undetermined by the above condition (because otherwise three pairs $(a_i,b_i)$ lie on a single line, a condition that can be broken by an insignificant perturbation of the input).</p>

<p>Given any $x$ and two such indices $i$ and $j$, consider the neighboring points $x'$ and $x''$ obtained by raising $x_i$ to $1$ and lowering $x_j$ to 0, or vice versa.  Since $f$ is convex, one of these points is as good as $x$, that is, $\max\{f(x'),f(x'')\} \ge f(x)$.</p>

<p>Finally, to find the best $S$ in polynomial time, determine the $n\choose 2$ breakpoints $\pi$ such that $a_i + b_i\pi = a_j  + b_j \pi$ for some $i$ and $j\ne i$.  For each such $\pi$, order the indices $i$ by $a_i + b_i \pi$, and take $S$ to contain the first $k$ indices in the order (if there is a tie for the $k$th, there are at most two indices that are tied; try both, giving two sets $S$ for that $\pi$).  Take whichever of these at most $2{n\choose 2}$ sets $S$ gives the largest $f(S)$.</p>

CC BY-SA 3.0
2017-03-09T19:11:18.627Z
2017-03-09T19:45:23.027Z
2017-03-09T19:45:23.027Z
Neal Young
<p>Are the following two problems NP-hard?</p>

<p><strong>Problem 1</strong></p>

<p>Given $n$ ordered pairs of integers $S=\{(a_i,b_i)\}$, $1\leq i \leq n$, and an integer $k$.</p>

<p>Find a subset $A$ of $S$ with $k$ elements, such that $\sum_{(a,b) \in A}a+\prod_{(a,b) \in A}b$ is maximized.</p>

<hr>

<p><strong>Problem 2</strong></p>

<p>Given $n$ ordered pairs of real numbers $S=\{(a_i,b_i)| 0 \leq a_i \leq 1, 1 - a_i \leq b_i \leq 1\}$, $1\leq i \leq n$, and an integer $k$.</p>

<p>Find a subset $A$ of $S$ with $k$ elements, such that $\sum_{(a,b) \in A}a-\prod_{(a,b) \in A} b$ is maximized.</p>

<p>Or, equivalently:</p>

<p>Given $n$ ordered pairs of real numbers $S=\{(a_i,c_i)| 0 \leq a_i, c_i, \leq 1\}$, $1\leq i \leq n$, and an integer $k$, find a subset $A$ of $S$ with $k$ elements, such that $\sum_{(a,c) \in A}a-\prod_{(a,c) \in A}(1-ac)$ is maximized.</p>

<hr>

<p>The objectives can be taken as set functions defined on $2^S$. The objective of the second problem is submodular. </p>

<p>Any hint, reference to a book, a paper or related problems is appreciated.
I have tried finding a reduction from knapsack and set cover, but no luck so far.</p>

CC BY-SA 3.0
2015-11-07T11:05:00.900Z
What have you already tried?
Boson
CC BY-SA 3.0
2015-11-07T23:20:12.297Z
@Boson I have tired knapsack and set cover but did not make it. I am also  trying 3-SAT.
Arthur
CC BY-SA 3.0
2015-11-12T20:14:27.913Z
Do you have a candidate for a family of hard problem instances?  Here's my best attempt: choose all the $a_i$'s such that $a_i \approx 1$, then choose $b_i \approx (k(2-a_i))^{1/k}$ (with a tiny bit of random noise in the $a_i$'s, $b_i$'s).  With this choice, the objective function has value $\approx 2k$ for every set $A$, and I don't see an obvious algorithm (some sort of greedy thing would be the natural thing to try, but in analyzing possible strategies I get bogged down in reasoning about the gap between the best and second-best solution, and # of bits of precision issues).
D.W.
CC BY-SA 3.0
2015-12-01T20:26:12.553Z
@Boson Thanks for editing. For the decision version of problem 1, I am trying to convert "the objective value is at least l" to "the objective value is equal to l". If this is possible, subset-sum may work by setting $(a_i,b_i)=(a_i \cdot p, q^{b_i})$ and $l=l_1\cdot p+q^{l_2}$, where q and p are certain primes and $l_1$ and $l_2$ are certain integers.
Arthur
<np-hardness><submodularity>
A maximization problem containing summation and multiplication
Arthur
# A maximization problem containing summation and multiplication

(Asked by: username_0 on 2015-11-07)

Are the following two problems NP-hard?

**Problem 1**

Given $n$ ordered pairs of integers $S=\{(a\_i,b\_i)\}$, $1\leq i \leq n$, and an integer $k$.

Find a subset $A$ of $S$ with $k$ elements, such that $\sum\_{(a,b) \in A}a+\prod\_{(a,b) \in A}b$ is maximized.

---

**Problem 2**

Given $n$ ordered pairs of real numbers $S=\{(a\_i,b\_i)| 0 \leq a\_i \leq 1, 1 - a\_i \leq b\_i \leq 1\}$, $1\leq i \leq n$, and an integer $k$.

Find a subset $A$ of $S$ with $k$ elements, such that $\sum\_{(a,b) \in A}a-\prod\_{(a,b) \in A} b$ is maximized.

Or, equivalently:

Given $n$ ordered pairs of real numbers $S=\{(a\_i,c\_i)| 0 \leq a\_i, c\_i, \leq 1\}$, $1\leq i \leq n$, and an integer $k$, find a subset $A$ of $S$ with $k$ elements, such that $\sum\_{(a,c) \in A}a-\prod\_{(a,c) \in A}(1-ac)$ is maximized.

---

The objectives can be taken as set functions defined on $2^S$. The objective of the second problem is submodular.

Any hint, reference to a book, a paper or related problems is appreciated.
I have tried finding a reduction from knapsack and set cover, but no luck so far.

**Tags:** np-hardness, submodularity

> **Comments:**
> **username_1**: What have you already tried?  
> **username_0**: @username_1 I have tired knapsack and set cover but did not make it. I am also  trying 3-SAT.  
> **username_2**: Do you have a candidate for a family of hard problem instances?  Here's my best attempt: choose all the $a_i$'s such that $a_i \approx 1$, then choose $b_i \approx (k(2-a_i))^{1/k}$ (with a tiny bit of random noise in the $a_i$'s, $b_i$'s).  With this choice, the objective function has value $\approx 2k$ for every set $A$, and I don't see an obvious algorithm (some sort of greedy thing would be the natural thing to try, but in analyzing possible strategies I get bogged down in reasoning about the gap between the best and second-best solution, and # of bits of precision issues).  
> **username_0**: @username_1 Thanks for editing. For the decision version of problem 1, I am trying to convert "the objective value is at least l" to "the objective value is equal to l". If this is possible, subset-sum may work by setting $(a_i,b_i)=(a_i \cdot p, q^{b_i})$ and $l=l_1\cdot p+q^{l_2}$, where q and p are certain primes and $l_1$ and $l_2$ are certain integers.  

---

## 1 answers

### Answer by username_3 on 2017-03-09. Score: 4 | Accepted answer

I think both of your problems are in P. Here's an algorithm that works in P without any restriction on the $(a\_i,b\_i)$ pairs.

Formulate your problem as the problem of choosing $x\in\{0,1\}^n$ subject to $\sum\_i x\_i = k$ so as to maximize
$$\textstyle f(x) = \pi(x) + \sum\_i x\_i a\_i$$
where $\pi(x)=\prod\_i \exp( x\_i \beta\_i)$ and $\beta\_i = \ln b\_i$. Relax the problem to allow $x\in[0,1]^n$.

For intuition, note that the function $f(x)$ is convex, so it is maximized over $x\in[0,1]^n$ at some $x\in\{0,1\}^n$. (To see the latter, note that any $x\in [0,1]^n$ with $\sum\_i x\_i = k$ is the weighted average of integer points $x'$ in $\{0,1\}^n$ with $\sum\_i x'\_i = k$, and $f(x)$ is at most the corresponding weighted average of $f(x')$ over those integer points, so one of those integer points $x'$ has $f(x') \ge f(x)$.)

Anyhow, find an optimal integer solution $x$ in polynomial time as follows.
The first derivative of $f$ with respect to $x\_i$ is
$$\textstyle a\_i + b\_i\, \pi(x),$$
so (given the constraint $\sum\_i x\_i = k$), there exists $\lambda$ such that for the optimal $x\in[0,1]^n$,
$$x\_i = \begin{cases}
0 & \text{ if } a\_i + b\_i \pi(x) < \lambda \\
1 & \text{ if } a\_i + b\_i \pi(x) > \lambda \\
? & \text{ if } a\_i + b\_i \pi(x) = \lambda.
\end{cases}$$

Furthermore, WLOG there are at most two indices $i$ that are undetermined by the above condition (because otherwise three pairs $(a\_i,b\_i)$ lie on a single line, a condition that can be broken by an insignificant perturbation of the input).

Given any $x$ and two such indices $i$ and $j$, consider the neighboring points $x'$ and $x''$ obtained by raising $x\_i$ to $1$ and lowering $x\_j$ to 0, or vice versa. Since $f$ is convex, one of these points is as good as $x$, that is, $\max\{f(x'),f(x'')\} \ge f(x)$.

Finally, to find the best $S$ in polynomial time, determine the $n\choose 2$ breakpoints $\pi$ such that $a\_i + b\_i\pi = a\_j + b\_j \pi$ for some $i$ and $j\ne i$. For each such $\pi$, order the indices $i$ by $a\_i + b\_i \pi$, and take $S$ to contain the first $k$ indices in the order (if there is a tie for the $k$th, there are at most two indices that are tied; try both, giving two sets $S$ for that $\pi$). Take whichever of these at most $2{n\choose 2}$ sets $S$ gives the largest $f(S)$.


---

