Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Math Forum
»
Discussions
»
sci.math.*
»
sci.math
Notice: We are no longer accepting new posts, but the forums will continue to be readable.
Topic:
A maximization problem
Replies:
2
Last Post:
Jun 8, 2000 12:42 PM




Re: A maximization problem
Posted:
Jun 8, 2000 1:52 AM


ptyagi@mydeja.com writes: > given N vectors (a_i,b_i,c_i), where a_i,b_i,c_i are non negative > real numbers. Also, \sum_N b_i <=1. Find the subset S of vectors > which maximize the expression, > > \sum_S a_i  \sum_S c_i >  > 1  \sum_S b_i
It may be easier to ask for a fractional relaxation, i.e. a choice of values 0<=p_i<=1 maximizing sum(p_i a_i)/(1sum(p_i b_i))  sum(p_i c_i)
Your actual problem is the restriction that p_i should be in {0,1}.
For the fractional problem, if you know the value of lambda=(1sum(p_i b_i)), you can find the optimal assignment with a simple greedy algorithm: just repeatedly choose the i maximizing (ai/lambda  ci)/bi and set pi as large as possible until the sum of the pi's chosen so far equals lambda. Essentially, this is a kind of fractional knapsack problem.
You could then likely find the optimal lambda by various techniques e.g. binary search, Newton iteration, parametric search, etc. For a more detailed description of similar algorithms for a different fractional maximization problem, see my paper "Choosing subsets with maximum weighted average", http://www.ics.uci.edu/~eppstein/pubs/pmaxwtavg.html
Is the fractional solution ever different from the 01 solution you really want? I'm too tired right now to think about it clearly enough. If so, you're done. If not, the problem starts looking more like a 01 knapsack problem and could even be NPcomplete.  David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/



