Expected Number of Iterations of Interior-Point Algorithms for Linear Programming
Year: 2005
Journal of Computational Mathematics, Vol. 23 (2005), Iss. 1 : pp. 93–100
Abstract
We study the behavior of some polynomial interior-point algorithms for solving random linear programming (LP) problems. We show that the expected and anticipated number of iterations of these algorithms is bounded above by O(n1.5). The random LP problem is Todd's probabilistic model with the Cauchy distribution.
You do not have full access to this article.
Already a Subscriber? Sign in as an individual or via your institution
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/2005-JCM-8799
Journal of Computational Mathematics, Vol. 23 (2005), Iss. 1 : pp. 93–100
Published online: 2005-01
AMS Subject Headings:
Copyright: COPYRIGHT: © Global Science Press
Pages: 8
Keywords: Linear programming Interior point algorithms Probabilistic LP models Expected number of iterations.