Solving fractional packing problems in Oast(1/ε) iterations

摘要

We adapt a method proposed by Nesterov [16] to design an algorithm that computes ε-optimal solutions to fractional packing problems by solving O^*(ε^-1 √Kn) separable convex quadratic programs, where K is the maximum number of non-zeros per row and n is the number of variables. We also show that the quadratic program can be approximated to any degree of accuracy by an appropriately defined piecewise-linear program. For the special case of the maximum concurrent flow problem on a graph G =(V,E) with rational capacities and demands we obtain an algorithm that computes an Ε-optimal flow by solving O*(ε^-1 K^3/2|E| √|V| (log 1/ε+ LU + LD)) shortest path problems, where K is the number of commodities, and LU, LD are, respectively, the number of bits needed to store the capacities and demands. We also show that the complexity of computing a maximum multicommodity flow is O^*(1/εlog2(1/ε)). In contrast, previous algorithms required Ω(ε^-2) iterations.