zbMATH — the first resource for mathematics

A strongly polynomial algorithm to solve combinatorial linear programs. (English) Zbl 0626.90053
A polynomial linear programming algorithm that solves max(cx: $$x\geq 0$$, $$Ax=b)$$ is proposed. The algorithm consists of the elementary arithmetic operations only, and the number of those operations depends only on the size of the entries (being, in fact, rational numbers) in the constraint matrix A. On the other hand the complexity of the algorithm is independent of the size of the entries in c and of those in b. The algorithm can be applied to solve the minimum cost flow and the multicommodity flow problems.
Reviewer: W.Stanczak

MSC:
 90C05 Linear programming 68Q25 Analysis of algorithms and problem complexity 90C27 Combinatorial optimization 90C06 Large-scale problems in mathematical programming 65K05 Numerical mathematical programming methods
Full Text: