Loading [MathJax]/jax/output/CommonHTML/jax.js
Journals
Resources
About Us
Open Access
Go to previous page

Expected Number of Iterations of Interior-Point Algorithms for Linear Programming

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.