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(n^{1.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.