1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Greedy Algorithm for license purchase problem

  1. Nov 16, 2008 #1
    Your friends are starting a security company that needs to obtain licenses for n different pieces of cryptographic software. Due to regulations, they can only obtain these licenses at the rate of at most one per month.

    Each license is currently selling for a price of $100. However, they are all becoming more expensive according to exponential growth curves: in particular, the cost of license j increases by a factor of rj > 1 each month, where rj is a given parameter. This means that if license j is purchased t months from now, it will cost 100×rtj . We will assume that all the price growth rates are distinct.

    The question is: Given that the company can only buy at most one license a month, in which order should it buy the licenses so that the total amount of money it spends is as small as possible?
  2. jcsd
  3. Nov 16, 2008 #2
    I think you left something out. Order doesn't seem to make any difference. Am I missing something???
  4. Nov 16, 2008 #3
    Of course order makes a difference.

    Assume I have license 1 with rate t^3 and license 2 with rate 2^t - now these rates are exponential and there is no easy way to determine the correct growth rate (derivates are wrt to "t" as well), so how can you ensure you pick the right one first so that at (t+1) you don't end up having to spend more because license 2 now costs a lot more then license 1 would have?

    So, depending on time (t) the price will be different, and seeing as all rates are different some things will become much more expensive then others as time goes on, those should be bought first.
  5. Nov 16, 2008 #4
    I am not sure if I understood the question properly, so I am expressing what I understand, and you can correct me if there is a misunderstanding.

    " A company needs to buy n different software licences. The cost of licence type j in month t from a given reference date is given by
    C(j,t)=100*r(j)t, j=1...n
    where r(j) is the growth factor of the licence of type j.
    If the company can afford to buy 1 licence per month, what is the optimal buying strategy in the choice of the order buying the n licences?
    Assume that the company buys the first licence at time t=0."

    The objective is to minimise
    Sum(C(j,t)) for t=0,n-1
    by using a logical choice of j each month.
    Since it is an exponential function, ASSUMING r(j)>1, its seems logical (to be verified) to use the inverse of the greedy algorithm, namely, pick the least expensive at time t=n-1, n-2, .... etc., i.e. pick the last one first. If r(j)<1, then it is logical to buy the least expensive each month as time goes on (t=0 to t=n-1).
  6. Nov 16, 2008 #5
    Nope - you pretty hit it right on...
    That is what I was thinking also - start at month (n) - the last month - and calculate the rate, then choose the smallest one and buy it, and proced to month (n-1).

    Thanks for the confirmation.
    Much appreciated.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook