Abstract
A modified Karmarkar logarithmic potential is used in the framework of unrestricted Lagrangian decomposition to develop a fast approximation scheme for nonnegative convex block angular min-max resource sharing problems having K blocks and M block-separable coupling inequalities. For a given relative accuracy ε [0,1], the proposed algorithm can be implemented to run in O (logε-1) scaling phases that provide progressively more accurate solutions. Each scaling phase requires approximate solutions of K independent problems on the original blocks, to comparable accuracy. It is shown that ε-approximate solutions of this block angular problem and of its Lagrangian dual can be computed in a total of O (Mε-2) coordination steps over all scaling phases, disregarding logarithmic factors. The method can be specialized to a variety of structured network models, including minimum-cost Kcommodity flows in M-arc capacitated digraphs. For the latter problem, the proposed algorithm runs in O (KM 2ε-2) time, disregarding logarithmic factors.