Selected works (Q2920268)

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.NEWLINENEWLINEThe 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.NEWLINENEWLINEPart 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.NEWLINENEWLINEPart 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 [\textit{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.NEWLINENEWLINEPart 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.NEWLINENEWLINEPart 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.NEWLINENEWLINEPart 5 contains reminiscences of co-authors and colleagues of L. G.~Khachiyan.