A Primer on Karmarkar's Algorithm for Linear Programming

Date

1985

Author

Paris, Quirino

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

29
views

12
downloads

Cite This

A new algorithm for solving linear programs has been proposed recently by N. Karmarkar. Instead of hopping from extreme point to extreme point along the boundary of the solution set, as the simplex method does, Karmarkar's algorithm cuts across the set of feasible solutions. As a solution procedure for solving very large-scale linear programming problems, the new algorithm shows great potential. In this paper, Karmarkar's algorithm is described. Also, although Karmarkar's paper does not provide any explicit discussion of duality, it is shown that in this algorithm dual variables and dual relations are alive and well. Finally the degeneracy and multiple optimal solution issues are discussed with respect to the new algorithm.

URI

https://hdl.handle.net/11511/112697

Collections

Department of Economics, Article