A Unified Approach for Design of Lp Polynomial Algorithms

By summarizing Khachiyan's algorithm and Karmarkar's algorithm forlinear program (LP) a unified methodology for the design of polynomial-time algorithms for LP is presented in this paper. A key concept is the so-called extended binary search (EBS) algorithm introduced by the author. It is used as a unified model to analyze the complexities of the existing modem LP algorithms and possibly, help designing new algorithms with polynomial-time iterations for problems in other areas.

Keywords:

Extended Binary Search , Khachiyan's Algorithm , Karmarkar 's Algorithm , Khachiyan's Algorithm , Karmarkar 's Algorithm , Unified Methodology