3
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.