Linear programming, complexity. Separation and optimization.

Publication date 5 September 2002

Published in Mathématiques \& Applications (Berlin) (Search for Journal in Brave)

algorithmic complexity complexity analysis ellipsoid method linear programming Turing machine

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming (90-01) Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Mathematical programming (90Cxx)

Review text

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.

Recommendations

This page was built for publication: Linear programming, complexity. Separation and optimization.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1612911)