Khachiyan's linear programming algorithm

DOI10.1016/0196-6774(80)90002-4MaRDI QIDQ3880575zbMATH OpenOpenAlexFDO

Authors Bengt Aspvall, Richard E. Stone

Publication date 1980

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(80)90002-4

zbMATH Keywords

system of linear inequalitiespolynomial time algorithmellipsoidsKhachiyan's algorithmellipsoidal algorithmsmultidimensional bisection algorithmweak inequality system

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25)

Cited in

(7)

• A fully polynomial time projective method
• Khachiyan's Algorithmus
• A polynomial Newton method for linear programming
• An extension of Karmarkar's algorithm for solving a system of linear homogeneous equations on the simplex
• Identities in upper triangular tropical matrix semigroups and the bicyclic monoid
• On Estimating Optimal Bases for Linear Programs
• Complexity of linear programming

This page was built for publication: Khachiyan's linear programming algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3880575)