The Math Forum



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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   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
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply



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/







Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.