Are the following two problems NP-hard?Problem 1Given $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 2Given $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.
A maximization problem containing summation and multiplication
np hardness;submodularity
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)$.