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

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: DOI