×

zbMATH — the first resource for mathematics

A strongly polynomial algorithm for linear systems having a binary solution. (English) Zbl 1268.90029
The paper describes a strongly polynomial algorithm which either finds a solution to a linear system with integer coefficients, or correctly decides that the system does not have 0,1-solutions. The algorithm can be used as a basis for the construction of a polynomial algorithm for linear programming, which differs substantially from the well-known polynomial algorithms. The most important properties on which the method is based are the (Hahn-Banach) separation theorem for disjoint convex sets and the Cauchy-Schwarz inequality.

MSC:
90C05 Linear programming
90C09 Boolean programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Agmon Sh.: The relaxation method for linear inequalities. Can. J. Math. 6, 382–392 (1954) · Zbl 0055.35001 · doi:10.4153/CJM-1954-037-2
[2] Chubanov, S.: A polynomial relaxation-type algorithm for linear programming. http://www.optimization-online.org/DB_HTML/2011/02/2915.html (2010)
[3] Edmonds J.: Systems of distinct representatives and linear algebra. J. Res. Nat. Bur. Standards 71B, 241–245 (1967) · Zbl 0178.03002 · doi:10.6028/jres.071B.033
[4] Karmarkar N.: A new polynomial-time algorithm for linear programming. Combinatorica 4, 353–395 (1984) · Zbl 0557.90065 · doi:10.1007/BF02579150
[5] Khachiyan, L.G.: A polynomial algorithm in linear programming. Dokl. Akad. Nauk SSSR 244 (English translation: Soviet Math. Dokl. 20, 191–194) (1979) · Zbl 0414.90086
[6] Motzkin Th., Schoenberg I.J.: The relaxation method for linear inequalities. Can. J. Math. 6, 393–404 (1954) · Zbl 0055.35002 · doi:10.4153/CJM-1954-038-x
[7] Tardos E.: A strongly polynomial algorithm to solve combinatorial linear programs. Oper. Res. 34, 250–256 (1986) · Zbl 0626.90053 · doi:10.1287/opre.34.2.250
[8] Todd M.: The many facets of linear programming. Math. Programm. 91, 417–436 (2002) · Zbl 1030.90051 · doi:10.1007/s101070100261
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.