Welcome to our community

Be a part of something great, join today!

Improvement algorithm and its time complexity

malamenm

New member
Apr 4, 2013
5
Hi, I have a problem with the following problem:

Assume fj is concave and strictly increasing for all j, j=1,..,n. Show that the optimal solution x* satisfies the condition (from j=1 to n) ∑x*j=B.

Now consider the following improvement algorithm:

start with x0=0 for k=1:B

select s∈argmaxj{fj(xjk-1+1)-fj(xjk-1}
update xk s.t. xjk=xjk-1 for j≠s, and xsk=xsk-1+1
end
x bar = xB

I am trying to find the time complexity of the algorithm and to show that x bar is an optimal solution (i.e. the algorithm above is an exact algorithm if fj is concave and strictly increasing for all j, j=1,..,n)

Does anybody have any suggestions on how to start on this?

Any help will be much appreciated