A maximization problem containing summation and multiplication

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.

• What have you already tried? – Boson Nov 7 '15 at 11:05
• @Boson I have tired knapsack and set cover but did not make it. I am also trying 3-SAT. – Arthur Nov 7 '15 at 23:20
• 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. Nov 12 '15 at 20:14
• @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 Dec 1 '15 at 20:26

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)$.