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.

Improve this question
$\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$
    – Greg Martin
    Commented Nov 1, 2011 at 20:25

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Just try the $n$ vertices one by one! $\endgroup$
    – fedja
    Commented 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
    Commented Nov 1, 2011 at 23:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .