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

ellipsoidal algorithmsellipsoidsKhachiyan's algorithmmultidimensional bisection algorithmpolynomial time algorithmsystem of linear inequalitiesweak inequality system

Mathematics Subject Classification ID

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

Cited in

(8)

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

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)