- Thread starter
- #1

Assume f

^{j}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 x

^{0}=0 for k=1:B

select s∈argmax

_{j}{f

_{j}(x

_{j}

^{k-1}+1)-f

_{j}(x

_{j}

^{k-1}}

update x

^{k}s.t. x

_{j}

^{k}=x

_{j}

^{k-1}for j≠s, and x

_{s}

^{k}=x

_{s}

^{k-1}+1

end

x bar = x

^{B}

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