×

Selected works. (Изьранные труды.) (Russian) Zbl 1261.01016

Moskva: Izd. MTsNMO (ISBN 978-5-94057-509-2/hbk). 519 p. (2009).
This book is published in memory of L. G. Khachiyan and contains his selected works on complexity bounds of optimization and game problems, and also of enumeration and generation problems in combinatorics. His famous proof of the polynomial complexity of linear programming based on an application of the ellipsoid method became a classical result.
The book contains a preface, five parts (chapters), a list of publications by L. G. Khachiyan, and a name index. The preface part includes forewords by the editor S. P. Tarasov and by A. S. Nemirovskiĭ, and a short biography of L. G. Khachiyan. The first foreword describes the total structure of the book, whereas the second is devoted to the polynomial complexity of linear programming and related questions.
Part 1 contains two papers on matrix game algorithms. The first paper establishes a lower bound for a fictitious play-type algorithm, the second describes an approximate probabilistic algorithm for matrix games with sublinear complexity.
Part 2 is the main one and contains the results on complexity bounds of optimization. First of all, there is the D.Sc. dissertation of Khachiyan, the first paper on the polynomial complexity of linear programming [L. G. Khachiyan, Dokl. Akad. Nauk SSSR 244, 1093–1096 (1979); translation in Sov. Math., Dokl. 20, 191–194 (1979; Zbl 0409.90079)], a separate proof of this result by Khachiyan, the extended version of the first paper, and some related results on the polynomial complexity of quadratic programming, the inscribed ellipsoid method, diagonal matrix scaling, complexity of semi-definite programming problems and some other optimization problems with special structure.
Part 3 consists of a survey by V. A. Gurvich on efficiency and complexity in enumeration problems, and also three works on enumeration and generation problems in combinatorics.
Part 4 includes papers on different topics, such as probabilistic algorithms for discrete optimization, complexity of volume calculation of polyhedra, evaluation of Markov chain parameters, and a solution of cyclic games.
Part 5 contains reminiscences of co-authors and colleagues of L. G. Khachiyan.

MSC:

01A75 Collected or selected works; reprintings or translations of classics
90-03 History of operations research and mathematical programming
91-03 History of game theory, economics, and finance
05-03 History of combinatorics
90C05 Linear programming
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
01A70 Biographies, obituaries, personalia, bibliographies

Biographic References:

Khachiyan, Leonid G.
PDFBibTeX XMLCite