A strongly polynomial algorithm for linear systems having a binary solution (Q715067): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Removed claim: reviewed by (P1447): Item:Q589946
RedirectionBot (talk | contribs)
Changed an Item
Property / reviewed by
 
Property / reviewed by: Maxim Ivanov Todorov / rank
 
Normal rank

Revision as of 17:03, 19 February 2024

scientific article
Language Label Description Also known as
English
A strongly polynomial algorithm for linear systems having a binary solution
scientific article

    Statements

    A strongly polynomial algorithm for linear systems having a binary solution (English)
    0 references
    0 references
    15 October 2012
    0 references
    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.
    0 references
    linear programming
    0 references
    polynomial algorithm
    0 references
    integer solutions
    0 references

    Identifiers