A linear programming primer: from Fourier to Karmarkar

DOI10.1007/s10479-019-03186-2zbMath1442.90122OpenAlexW2919984904WikidataQ128306283 ScholiaQ128306283MaRDI QIDQ2177789

Atlanta Chakraborty, Vijay Chandru, M. R. Rao

Publication date: 6 May 2020

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-019-03186-2

zbMATH Keywords

monotonelinear programmingdualityinterior point methodsimplex methodoptimisationlinear inequalitiesellipsoid method

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On Fourier's algorithm for linear arithmetic constraints
• A new polynomial-time algorithm for linear programming
• The simplex method. A probabilistic analysis
• The ellipsoid method and its consequences in combinatorial optimization
• Geometric algorithms and combinatorial optimization
• Fourier-Motzkin elimination and its dual
• The generalized simplex method for minimizing a linear form under linear inequality restraints
• Variable Elimination in Linear Constraints
• Towards a Genuinely Polynomial Algorithm for Linear Programming
• Fourier's Method of Linear Programming and Its Dual
• The Simplex and Projective Scaling Algorithms as Iteratively Reweighted Least Squares Methods
• A Strongly Polynomial Algorithm for a Special Class of Linear Programs
• On Finding Primal- and Dual-Optimal Bases
• Commentary—Progress in Linear Programming
• Commentary—Theory and Practice for Interior-Point Methods
• Lectures on Polytopes
• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• Improved Algorithms For Linear Inequalities with Two Variables Per Inequality
• On Linear Characterizations of Combinatorial Optimization Problems
• From LP to LP: Programming with constraints
• A Technique for Resolving Degeneracy in Linear Programming
• Convergence rate of the gradient descent method with dilatation of the space
• Polyhedral sets having a least element
• Optimality and Degeneracy in Linear Programming