A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs

Khachiyan, and recently Karmarkar, gave polynomial algorithms to solve the linear programming problem. These algorithms have a small theoretical drawback; namely, the number of arithmetic steps depends on the size of the input numbers. We present a polynomial linear programming algorithm whose number of arithmetic steps depends only on the size of the numbers in the constraint matrix, but is independent of the size of the numbers in the right-hand side and objective vectors. In particular, it gives a polynomial algorithm for the minimum cost flow and multicommodity flow problems in which the number of arithmetic steps is independent of the size of the costs and capacities. The algorithm makes use of an existing polynomial linear programming algorithm. The problem of whether any algorithm has a running time that is independent even of the size of the numbers in the constraint matrix remains open.