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 Free Access

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


Brown University The Quarterly of Applied Mathematics
is distributed by the American Mathematical Society
for Brown University
Online ISSN 1552-4485; Print ISSN 0033-569X
© 2017 Brown University
Comments: qam-query@ams.org
AMS Website