turkmath.org

A great many practical problems from wide areas of industry, business, and science can be modeled as Linear Programming (LP) problem. Therefore, design and analysis of efficient algorithms for LP problem are of great importance. In this talk we will review iteration complexity of several main LP algorithms. First, it will be shown that LP problem is not NP-complete which indicates a possibility that the polynomial algorithm may exists. Next, the complexity of much celebrated Simplex Algorithm will be discussed. It will be shown that unfortunately Simplex Algorithm has exponential worst-case complexity. However, the average-case complexity is much better; it is polynomial, which theoretically explains the success and good behavior of the algorithm that is usually observed in practical applications. In the sequel, the complexity of the Ellipsoidal Algorithm will be discussed. Its importance comes from the fact that it was the first algorithm for LP with polynomial worst-case complexity. However, the importance was mainly theoretical because it was soon shown that it does not perform well in practice. In fact, in most instances the Ellipsoid Algorithm performs worse than the Simplex Algorithm. Finally, a class of recently developed Interior-Point Algorithms will be introduced. Success of these algorithms is based on the fact that their worst-case complexity is polynomial and, in addition, they perform well in practical applications often outperforming the Simplex Algorithm applied to the same problem. The average-case complexity will also be discussed. However, the difference between the worst-case and average-case complexity of the Interior-Point Algorithms is not as significant as for the Simplex Algorithm.