7
$\begingroup$

Any ideas or references on how to approach this problem? Every element in a set has a parameter $p_i \geq 0$ and $c_i \geq 0$. The objective is to find a subset which maximizes

$\prod_{i \in S} p_i + \sum_{i \in S} c_i$

I tried to prove complexity results but was unsuccessful. My guess is that it is NP-Hard, but I cannot find a reduction from any known problem. A greedy heuristic which sequentially adds elements which give the highest increase works fine, but can give arbitrarily bad results.

$\endgroup$
1
  • 1
    $\begingroup$ Just wanted to mention that this can be reduced to the following problem: every element in a set has parameter $0\le p_i<1$ and $c_i>0$, and the objective is to maximize $\lambda \prod_{i\in S} p_i + \sum_{i\in S} c_i$ for a given real number $\lambda\ge1$. This follows since we always want to include any $i$ for which $p_i\ge1$. $\endgroup$ Nov 1, 2011 at 20:25

1 Answer 1

14
$\begingroup$

It is actually an easy one. Suppose that you were allowed to take any part of each item adding $tc_i$ and multiplying by $p_i^t$ for any $t\in[0,1]$. First, you should take everything that has $p_i\ge 1$ (because it never hurts). Then you have to maximize $C\prod_j e^{-b_j t_j}+\sum_j t_j c_j$ where $b_j=-\log p_j>0$. Now the points $(\sum t_j b_j, \sum t_j c_j)$ form a convex polygon and you know its boundary (half of it comes from arranging $c_j/b_j$ in the decreasing order and the other half from arranging them in the increasing order). Moreover, the functional $(x,y)\mapsto Ce^{-x}+y$ is convex, so its maximum is attained at some vertex on the boundary (which correspond to some subsets) and you are done in $n\log n$ time most of which is spent on sorting.

Now, if the task were to minimize that quantity, that would be worse than the knapsack packing problem.

$\endgroup$
2
  • 1
    $\begingroup$ Just try the $n$ vertices one by one! $\endgroup$
    – fedja
    Nov 1, 2011 at 23:29
  • $\begingroup$ Going over the perimeter from $(0,0)$, so that each vertex will require just one multiplication, 2 additions and one comparison, of course, not recomputing the full products, which would be $n^2$. $\endgroup$
    – fedja
    Nov 1, 2011 at 23:50

Your Answer

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

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