Speeding up Karmarkar’s algorithm for multicommodity flows

The authors show how to speed up Karmarkar’s linear programming algorithm for the case of multicommodity flows. The special structure of the constraint matrix is exploited to obtain an algorithm for the multicommodity flow problem which requires O(s³’.⁵v²’.⁵eL) arithmetic operations, each operation being performed to a precision of O(L) bits. Here v is the number of vertices and e is the number of edges in the given network, s is the number of commodities, and L is bounded by the number of bits in the input. The authors obtain a speed up of the order of (e⁰’.⁵/v⁰’.⁵)+(e²’.⁵/v²’.⁵s²) over Karmarkar’s modified algorithm which is substantial for dense networks. The techniques in the paper can also be used to speed up any interior point algorithm for any linear programming problem whose constraint matrix is structurally similar to the one in the multicommodity flow problem.