1988 | OriginalPaper | Buchkapitel
The Ellipsoid Method
verfasst von : Martin Grötschel, László Lovász, Alexander Schrijver
Erschienen in: Geometric Algorithms and Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In 1979 a note of L. G. Khachiyan indicated how an algorithm, the so-called ellipsoid method, originally devised for nonlinear nondifferentiable optimization, can be modified in order to check the feasibility of a system of linear inequalities in polynomial time. This result caused great excitement in the world of mathematical programming since it implies the polynomial time solvability of linear programming problems.