Science World Journal

Log in or Register to get access to full text downloads.

Remember me or Register

Comparative analysis of the affine scaling and Karmarkar’s polynomial – time for linear programming

B.O Adejo, D.N Choji


The simplex method is the well-known, non-polynomial solution technique for linear programming problems. However, some computational testing has shown that the Karmarkar’s polynomial projective interior point method may perform better than the simplex method on many classes of problems, especially, on problems with large sizes. The affine scaling algorithm is a variant of the Karmarkar’s algorithms. In this paper, we compare the affine scaling and the Karmarkar algorithms using the same test LP problem.

Keywords: Polynomial-time, Complexity bound, Primal LP, Dual LP, Basic Solution, Degenerate Solution, Affine Space, Simplex and Polytope
AJOL African Journals Online