A polynomial-time algorithm, based on Newton's method, for linear programming

James Renegar

Type: Article

Publication Date: 1988-01-01

Citations: 590

DOI: https://doi.org/10.1007/bf01580724

View Publication

Locations

Mathematical Programming - View

Similar Works

Action	Title	Year	Authors
+	A polynomial newton method for linear programming	1986	Guy de Ghellinck J.‐P. Vial
+	A polynomial Newton method for linear programming	1986	G. de Ghelli Nck Jean-Philippe Vial
+	A polynomial-time simplex type method for solving linear systems of inequalities	1990	L.M. Bregman
+	The use of Newton's method for linear programming	1995	Yu. G. Yevtushenko V. G. Zhadan A. P. Cherenkov
+	A comparative study of a polynomial-time algorithm with some non-polynomially bounded methods for linear programming	2013	B. O. Adejo
+	An efficient algorithm for linear programming	1990	V. Ch. Venkaiah
+	An algorithm for the solution of linear programming problems.	1968	Donald Leroy Sparks
+	An algorithm for linear programming that is easy to implement	1989	J.C. Culioli V. Protopopescu
+ PDF Chat	A new algorithm for solving linear programming problems	2012	Andrés Leonardo Ramírez Leal Óscar Yecid Buitrago Suescún Rodrigo Alberto Britto Agudelo
+	A polynomial-time algorithm for a class of linear complementarity problems	1989	Masakazu Kojima Shinji Mizuno Akiko Yoshise
+	An Algorithm to Solve a Linear Program.	2006	Rajan Alex
+	A method of solving linear and convex programming problems	1970	Ya. M. Bershchanskii
+	An approximate algorithm for the solution of the linear programming problem	1974	V.Yu. Lebedev
+	An efficient Newton's method for optimization under equality constraints	1976	Bart Childs Melvin J. Maron
+	A simple polynomial-time algorithm for convex quadratic programming	1988	Paul Tseng Decision Systems.
+	A class of methods for linear programming	1978	Markku Kallio Evan L. Porteus
+	A parallel algorithm for linear programming problems	1992	Dzh. A. Babayev Sahib S. Mardanov
+	Karmarkar's linear programming algorithm and Newton's method	1991	David Bayer Jeffrey C. Lagarias
+	An interior-point method for linear and quadratic programming problems	1991	Paul T. Boggs Paul D. Domich Janet E. Rogers Christoph Witzgall
+	A quadratic programming algorithm for large and sparse problems	1991	Miroslav Tůma

Works That Cite This (470)

Action	Title	Year	Authors
+ PDF Chat	Interior point methods 25 years later	2011	Jacek Gondzio
+	Speeding-up linear programming using fast matrix multiplication	1989	Pravin M. Vaidya
+	Interior Point Methods for Linear Optimization	2005	C. Roos Tamás Terlaky J.‐P. Vial
+ PDF Chat	Solving Linear Programs in the Current Matrix Multiplication Time	2021	Michael B. Cohen Yin Tat Lee Zhao Song
+ PDF Chat	The Bit Complexity of Efficient Continuous Optimization	2023	Mehrdad Ghadiri Richard Peng Santosh Vempala
+	On the Complexity of a Column Generation Algorithm for Convex or Quasiconvex Feasibility Problems	1994	Jean‐Louis Goffin Zhi‐Quan Luo Yinyu Ye
+	On the finite convergence of interior-point algorithms for linear programming	1992	Yinyu Ye
+	A cutting plane method from analytic centers for stochastic programming	1995	Olivier Bahn O. du Merle Jean‐Louis Goffin J.‐P. Vial
+	Linear Programming in O([n3/ln n]L) Operations	1999	Kurt M. Anstreicher
+	Maximum entropy Gaussian approximation for the number of integer points and volumes of polytopes	2009	Alexander Barvinok J. A. Hartigan

Works Cited by This (7)

Action	Title	Year	Authors
+	An algorithm for linear programming which requires O(((m+n)n 2+(m+n)1.5 n)L) arithmetic operations	1990	Pravin M. Vaidya
+	Polynomial algorithms in linear programming	1980	Leonid Khachiyan
+	Towards an asymptotic analysis of Karmarkar's algorithm	1986	Lenore Blum
+ PDF Chat	On the efficiency of algorithms of analysis	1985	Steve Smale
+	An "analytical centre" for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming	2006	Gy. Sonnevend
+ PDF Chat	Boundary Behavior of Interior Point Algorithms in Linear Programming	1989	Nimrod Megiddo Michael Shub
+	Nonlinear Programming	1967	K. B. Haley