Quarterly of Applied Mathematics

Quarterly of Applied Mathematics

Online ISSN 1552-4485; Print ISSN 0033-569X



Khachiyan's algorithm for linear inequalities: optimization and implementation

Author: Frederic Bisshopp
Journal: Quart. Appl. Math. 38 (1981), 415-426
MSC: Primary 90C05
DOI: https://doi.org/10.1090/qam/614550
MathSciNet review: 614550
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: An optimized version of Khachiyan's algorithm is developed here, and an APL implementation of it is provided. The operation count for $ M$ linear constraints on $ N$ variables is brought from the $ O\left( {{N^4}{M^2}} \right)$ of the original algorithm to $ O\left( {{N^4}M ln N} \right)$ with a smaller coefficient. There is no significant change of the storage requirement, which remains at $ O\left( {NM} \right)$ locations.

References [Enhancements On Off] (What's this?)

  • [1] L. G. Hačijan, A polynomial algorithm in linear programming, Dokl. Akad. Nauk SSSR 244 (1979), no. 5, 1093–1096 (Russian). MR 522052
  • [2] Translation of [1], Soviet Math. Doklady 20, 191-194 (1979)
  • [3] P. Gacs and L. Lovasz, Khachian's algorithm for linear programming, Computer Science Dept., Stanford University, 1979

Similar Articles

Retrieve articles in Quarterly of Applied Mathematics with MSC: 90C05

Retrieve articles in all journals with MSC: 90C05

Additional Information

DOI: https://doi.org/10.1090/qam/614550
Article copyright: © Copyright 1981 American Mathematical Society

American Mathematical Society