Khachiyan's linear programming algorithm

DOI10.1016/0196-6774(80)90002-4zbMath0438.90053OpenAlexW2047384482MaRDI QIDQ3880575

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

polynomial time algorithmellipsoidssystem of linear inequalitiesKhachiyan's algorithmellipsoidal algorithmsmultidimensional bisection algorithmweak inequality system

Mathematics Subject Classification ID

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

Related Items (7)

A polynomial Newton method for linear programming ⋮ A fully polynomial time projective method ⋮ On Estimating Optimal Bases for Linear Programs ⋮ 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 ⋮ Complexity of linear programming ⋮ Khachiyan's Algorithmus

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