Abstract
We present a Lagrangian decomposition algorithm which uses logarithmic potential reduction to compute an $varepsilon$-approximate solution of the general max-min resource sharing problem with $M$ nonnegative concave constraints on a convex set $B$. We show that this algorithm runs in $O(M({varepsilon^{-2}}+ln M))$ iterations, a data independent bound which is optimal up to polylogarithmic factors for any fixed relative accuracy $varepsilonin(0,1)$. In the general structured case, $B$ is the product of $K$ convex blocks and each constraint function is block separable. For such models, an iteration of our method requires a $Theta(varepsilon)$-approximate solution of $K$ independent block maximization problems which can be computed in parallel. (Research supported by the National Science Foundation under grant CCR-9618796.)