Linear programming, complexity. Separation and optimization. (Q1612911)

This book introduces to the complexity analysis of algorithms, measured by the amount of time needed by an implementation on a Turing machine. This amount of time is expressed as a worst-case function of the size of the problem, which is the amount of memory needed for storing it. The first chapters introduce the model of Turing machine and classes \({\mathcal P}\), \({\mathcal NP}\), and \({co \mathcal NP}\) of problems. A first application is the Gauss factorization algorithm for matrices; it is shown how a modification due to Edmonds allows to make it polynomial. Then in a second part the author deals with linear programming, analyses the simplex method, and then the ellipsoid method of Khachiyan that proved that linear programming problems could be solved polynomially. The book ends by analyzing the relations between separation from a polyhedra and optimization of a linear cost over a polyhedra. Unfortunately the book gives no indication on improvements of interior-point algorithms that allowed to decrease the estimates of complexity, and also to obtain efficient implementations. But this said, the book is a very useful introduction to the basic questions of algorithmic complexity, and should be helpful to many students and researchers.