A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs

Éva Tardos
Additional contact information
Éva Tardos: Rheinische Friedrich-Wilhelms-Universität, Bonn, West Germany

Operations Research, 1986, vol. 34, issue 2, 250-256

Abstract: 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.

Keywords: 730; strongly; polynomial; algorithm (search for similar items in EconPapers)
Date: 1986
References: Add references at CitEc
Citations: View citations in EconPapers (36)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.34.2.250 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:34:y:1986:i:2:p:250-256

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().