Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
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$. –  Greg Martin Nov 1 '11 at 20:25

1 Answer 1

up vote 13 down vote accepted

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.

share|improve this answer
1  
Just try the $n$ vertices one by one! –  fedja Nov 1 '11 at 23:29
    
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$. –  fedja Nov 1 '11 at 23:50
    
Thank you fedja!! –  sks Nov 2 '11 at 0:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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