Везде
THE MAKING AND EARLY DEVELOPMENT OF LINEAR-PROGRAMMING METHODS
Table of contents
Annotation Estimate Publication content
References Comments
Share
QR
Metrics
THE MAKING AND EARLY DEVELOPMENT OF LINEAR-PROGRAMMING METHODS
Annotation
PII
S0205-96060000513-1-1
Publication type
Article
Status
Published
Authors
Aleksandr Andrianov 
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
1117
Readers community rating
0.0 (0 votes)
Cite   Download pdf

References



Additional sources and materials

1. Andrianov, A. (2011) The Full Monge Problem Solution Base on the Linear Programming (LP), in Proceedings of the 8th Congress of the International Society for Analysis, its Applications, and Computation. Moscow: PFUR Press. pp. 220. 
 2. Andrianov, A. L. (2009) Kantorovich kak sozdatel' lineinogo programmirovaniia [Kantorovitch as the Founder of Linear Programming], Voprosy istorii estestvoznaniia i tekhniki, no. 4, pp. 77-89. 
 3. Andrianov, A. L. (2009) Razvitie lineinogo programmirovaniia v rannich rabotach L. V. Kantorovicha [Development of Linear Programming in the Early Works of L. V. Kantorovitch], Istoriko-matematicheskie issledovaniia, vtoraia seriia, no. 13 (48), pp. 323-339. 
 4. Andrianov, A. L. (2011) Razvitie lineinogo programmirovaniia v rabotach L. V. Kantorovicha 1930-50-kh godov [Development of Linear Programming in Works of L. V. Kantorovitch in the 1930s - 1950s], Istoriko-matematicheskie issledovaniia, vtoraia seriia, no. 14 (49), pp. 25-40. 
 5. Andrianov, A. L. (2014) Dzh. B. Dantsig i lineinoe programmirovanie [G. V. Dantzig and Lin­ear Programming], Kazanskaia nauka, no. 8, pp. 19-23. 
 6. Cook, S. A. (1971) The Complexity of Theorem Proving Procedures, in Proceedings of the Third Annual ACM Symposium on Theory of Computing, Shaker Heights, Ohio, USA, May 3-5, pp. 151-158. 
 7. Dantsig, Dzh. (Dantzig, G. B.) (1966) Lineinoe programmirovanie, ego primenenie i obobshcheniia [Linear Programming and Extensions]. Moskva: Progress. Edmonds, J. (1965) Paths, Trees, and Flowers, Canadian Journal of Mathematics, vol. 17, p. 449-467. 
 8. Grotschel, M., Lovasz, L., and Schrijver, A. (1981) The Ellipsoid Method and Its Consequences in Combinatorial Optimization, Combinatorica, vol. 1. pp. 169-197. 
 9. Iudin, D. B. and Nemiroskii A. S. (1976) Otsenka informatsionnoi slozhnosti zadach matematicheskogo programmirovaniia [The Estimation of Information Complexity of the Problems of Mathematical Programming], Ekonomika i matematicheskie metody, vol. 12, no. 1, pp. 118-142. 
 10. Iudin, D. B. and Nemiroskii, A. S. (1976) Informatsionnaia slozhnost' i effektivnye metody resheniia vypuklykh ekstremal'nykh zadach [Information Complexity and Efficient Meth­ods for Solving Convex Extreme Problems], Ekonomika i matematicheskie metody, vol. 12, no. 2, pp. 357-369. 
 11. Kantorovich, L. V. (1987) Moi put' v nauke [My Journey in Science], Uspekhi matemanicheskikh nauk, vol. 42, no. 2 (254), pp. 183-213. 
 12. Karmarkar, N. K. (1984) A New Polynomial-Time Algorithm for Linear Programming, Com­binatorica, vol. 4, no. 4. pp. 373-395. 
 13. Karp, R. M. (1972) Reducibility Among Combinatorial Problems, in: Miller, R. E., Thatch­er J. W. (eds.) Complexity of Computer Computations. New York: Plenum, pp. 85-103. 
 14. Khachiian, L. G. (1979) Polinomial'nyi algoritm v lineinom programmirovanii [Polynomial Algorithm in Linear Programming], Doklady AN SSSR, vol. 244, no. 5, pp. 1093-1096. 
 15. Khachiyan, L. G. (1979) A Polynomial Algorithm in Linear Programming, Soviet Mathematics Doklady, vol. 20, no. 1, pp. 191-194. 
 16. Klee, V. and Minty, G. J. (1969) How Good Is the Simplex Algorithm? in: Shisha, O. (ed.) Inequalities III (Proceedings of the Third Symposium on Inequalities Held at the University of California, Los Angeles, Calif., September 1-9, Dedicated to the Memory of Theodore S. Motzkin). New York and London: Academic Press, pp. 159-175. 
 17. Levin, A. Iu. (1965) Ob odnom algoritme minimizatsii vypukloi funktsii [On a Convex Func­tion Minimization Algorithm], Doklady AN SSSR, vol. 160, no. 6, pp. 1244-1247. 
 18. Levin, L. (1973) Universal'nye zadachi perebora [Universal Search Problems], Problemy peredachi informatsii, vol. 9, no. 3, pp. 115-116. 
 19. Magaril-Iliaev, G. G. and Tikhomirov, V. M. (2003) Vypuklyi analiz i ego prilozheniia. 2-e izd. [Convex Analysis and Its Applications. 2nd ed.]. Moskva: URSS. 
 20. Nemiroskii, A. S. and Iudin, D. B. (1977) Metody optimizatsii, adaptivnye k "sushchestvennoi" razmernosti zadachi [Optimization Methods Adaptable to the "Essential" Problem Dimen­sion], Avtomatika i telemekhanika, no. 4, pp. 75-87. 
 21. Todd, M. (2005) Leonid Khachiyan, 1952-2005: An Appreciation, SIAG/OPT Views-and-News, vol. 16, no. 1-2, pp. 4-6. 
 22. Yamnitsky, B. and Levin, L. (1982) An Old Linear Programming Algorithm Runs in Polyno­mial Time, in: 23rd Annual Symposium of Foundations of Computer Science, November 3-5, 1982, Chicago, Illinois, USA. New York, pp. 327-328.

Comments

No posts found

Write a review
Translate