- PII
- S0205-96060000513-1-
- DOI
- 10.31857/S60000513-1-1
- Publication type
- Article
- Status
- Published
- Authors
- Volume/ Edition
- Volume 38 / Issue 2
- Pages
- 351-361
- Abstract
- The paper reviews the making and early development of linear-programming methods (LPM) and how they influence the development of mathematics. The core problem that linked together many studies was the search for an effective polynomial way to tackle the tasks of linear programming. The paper analyzes the contributions of A. Yu. Levin (Levin - Newman method of central sections), A.S. Nemirovski (ellipsoid method), and L.G. Khachiyan (new approach-based proof of LPP polynomial-time solvability), and demonstrates the influence of the revolutionary work of N.K. Karmarkar who created an algorithm that converges to the solution by cutting through the feasible polyhedron instead of going along its boundary. The contribution of L. A. Levin who investigated the universal problems, complexity and reducibility is also considered.
- Keywords
- linear programming, optimization, Levin – Newman method of central sections, ellipsoid method, polynomial-time solvability, A. Yu. Levin, A.S. Nemirovski, L.G. Khachiyan, N.K. Karmarkar
- Date of publication
- 01.04.2017
- Number of purchasers
- 4
- Views
- 1174
RAS PresidiumVoprosy istorii estestvoznaniia i tekhniki
- ISSN (Print) 0205-9606
- ISSN (Online)2713-041X
THE MAKING AND EARLY DEVELOPMENT OF LINEAR-PROGRAMMING METHODS
Индексирование
Scopus
Crossref
Higher Attestation Commission
At the Ministry of Education and Science of the Russian Federation
Scientific Electronic Library