Published August 1987
| Published
Journal Article
Open
Convergence in Karmarkar's Algorithm for Linear Programming
- Creators
- Franklin, Joel
Abstract
Karmarkar's algorithm is formulated so as to avoid the possibility of failure because of unbounded solutions. A general inequality gives an easy proof of the convergence of the iterations. It is shown that the parameter value α = 0.5 more than doubles the originally predicted rate of convergence. To go from the last iterate to an exact optimal solution, an O(n^3) termination algorithm is prescribed. If the data have maximum bit length independent of n, the composite algorithm is shown to have complexity 0(n^4.5 log n).
Additional Information
©1987 Society for Industrial and Applied Mathematics. Received by the editors April 14, 1986; accepted for publication (in revised form) September 25, 1986.Attached Files
Published - FRAsiamjna87.pdf
Files
FRAsiamjna87.pdf
Files
(1.6 MB)
Name | Size | Download all |
---|---|---|
md5:f05170dd521e78291408d26411801a60
|
1.6 MB | Preview Download |
Additional details
- Eprint ID
- 13073
- Resolver ID
- CaltechAUTHORS:FRAsiamjna87
- Created
-
2009-02-05Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field