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.

کلیدواژه ها:

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