SPEEDING UP KARMARKARS ALGORITHM FOR MULTICOMMODITY FLOWS

摘要

We show how to speed up Karmarkar's linear programming algorithm for the case of multicommodity hows. The special structure of the constraint matrix is exploited to obtain an algorithm for the multicommodity flow problem which requires O(s(3.5)v(2.5)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. We obtain a speed up of the order of (e(0.5)/v(0.5)) + (e(2.5)/v(2.5)s(2)) 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. [References: 14]