Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

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

 Messages: [ Previous | Next ]
 eppstein@euclid.ics.uci.edu Posts: 128 Registered: 12/8/04
Re: A maximization problem
Posted: Jun 8, 2000 1:52 AM

ptyagi@my-deja.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)/(1-sum(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=(1-sum(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/p-maxwtavg.html

Is the fractional solution ever different from the 0-1 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 0-1
knapsack problem and could even be NP-complete.
--
David Eppstein UC Irvine Dept. of Information & Computer Science
eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/

Date Subject Author
6/6/00 ptyagi@my-deja.com
6/8/00 eppstein@euclid.ics.uci.edu
6/8/00 Hugo van der Sanden