Geometric algorithms and combinatorial optimization Grotschel M., Lovasz L., Schnjver A.

Grotschel M., Lovasz L., Schnjver A.
ISBN: 3-540-13624-Х | 0-387-13624-Х
Год: 1988
Издательство: Springer-Verlag
Количество страниц: 371
Язык: Английский
Формат: PDF / RAR

Формат файла: RAR

Historically, there is a close connection between geometry and optimization. This is illustrated by methods like the gradient method and the simplex method, which are associated with clear geometric pictures. In combinatorial optimization, however, many of the strongest and most frequently used algorithms are based on the discrete structure of the problems: the greedy algorithm, shortest path and alternating path methods, branch-and-bound, etc. In the last several years geometric methods, in particular polyhedral combinatorics, have played a more and more profound role in combinatorial optimization as well.
Our book discusses two recent geometric algorithms that have turned out to have particularly interesting consequences in combinatorial optimization, at least from a theoretical point of view. These algorithms are able to utilize the rich body of results in polyhedral combinatorics.
The first of these algorithms is the ellipsoid method, developed for nonlinear programming by N. Z. Shor, D. B. Yudin, and A. S. Nemirovskil It was a great surprise when L. G. Khachiyan showed that this method can be adapted to solve linear programs in polynomial time, thus solving an important open theoretical problem. While the ellipsoid method has not proved to be competitive with the simplex method in practice, it does have some features which make it particularly suited for the purposes of combinatorial optimization.
The second algorithm we discuss finds its roots in the classical "geometry of numbers", developed by Minkowski. This method has had traditionally deep applications in number theory, in particular in diophantine approximation. Methods from the geometry of numbers were introduced in integer programming by H. W, Lenstra. An important element of his technique, called basis reduction, goes in fact back to Hermite. An efficient version of basis reduction yields a polynomial time algorithm useful not only in combinatorial optimization, but also in fields like number theory, algebra, and cryptography.
A combination of these two methods results in a powerful tool for combinatorial optimization. It yields a theoretical framework in which the polynomial time solvability of a large number of combinatorial optimization problems can be shown quite easily. It establishes the algorithmic equivalence of problems which are "dual" in various senses.
Being this general, this method cannot be expected to give running times comparable with special-purpose algorithms. Our policy in this book is, therefore, not to attempt to obtain the best possible running times; rather, it is to derive just the polynomial time solvability of the problems as quickly and
painlessly as possible. Thus, our results are best conceived as "almost pure" existence results for polynomial time algorithms for certain problems and classes of problems.
Nevertheless, we could not get around quite a number of tedious technical details. We did try to outline the essential ideas in certain sections, which should give an outline of the underlying geometric and combinatorial ideas. Those sections which contain the technical details are marked by an asterisk in the list of contents. We therefore recommend, for a first reading, to skip these sections.
The central result proved and applied in this book is, roughly, the following. If К is a convex set, and if we can decide in polynomial time whether a given vector belongs to K, then we can optimize any linear objective function over К in polynomial time. This assertion is, however, not valid without a number of conditions and restrictions, and even to state these we have to go through many technical details. The most important of these is that the optimization can be carried out in an approximate sense only (as small compensation, we only need to test for membership in К in an approximate sense).
Due to the rather wide spread of topics and methods treated in this book, it seems worth while to outline its structure here.
Chapters 0 and 1 contain mathematical preliminaries. Of these, Chapter 1 discusses some non-standard material on the complexity of problems, efficiency of algorithms and the notion of oracles.
The main result, and its many versions and ramifications, are obtained by the ellipsoid method. Chapter 2 develops the framework necessary for the formulation of algorithmic problems on convex sets and the design of algorithms to solve these. A list of the main problems introduced in Chapter 2 can be found on the inner side of the back cover. Chapter 3 contains the description of (two versions of) the ellipsoid method. The statement of what exactly is achieved by this method is rather complicated, and the applications and specializations collected in Chapter 4 are, perhaps, more interesting. These range from the main result mentioned above to results about computing the diameter, width, volume, and other geometric parameters of convex sets. All these algorithms provide, however, only approximations.
Polyhedra encountered in combinatorial optimization have, typically, vertices with small integral entries and facets with small integral coefficients. For such polyhedra, the optimization problem (and many other algorithmic problems) can be solved in the exact sense, by rounding an approximate solution appropriately. While for many applications a standard rounding to some number of digits is sufficient, to obtain results in full generality we will have to use the sophisticated rounding technique of diophantine approximation. The basis reduction algorithm for lattices, which is the main ingredient of this technique, is treated in Chapter 5, along with several applications. Chapter 6 contains the main applications of diophantine approximation techniques. Besides strong versions of the main result, somewhat different combinations of the ellipsoid method with basis reduction give the strongly polynomial time solvability of several combinatorial optimization problems, and the polynomial time solvability of integer linear programming in fixed dimension, remarkable results of R Tardos and R W. Lenstra, respectively.
Chapters 7 to 10 contain the applications of the results obtained in the previous chapters to combinatorial optimization. Chapter 7 is an easy-to-read introduction to these applications. In Chapter 8 we give an in-depth survey of combinatorial optimization problems solvable in polynomial time with the methods of Chapter 6. Chapters 9 and 10 treat two specific areas where the ellipsoid method has resolved important algorithmic questions that so far have resisted direct combinatorial approaches: perfect graphs and submodular functions.
We are grateful to several colleagues for many discussions on the topic and text of this book, in particular to Bob Bixby, Andras Frank, Michael Junger, Gerhard Reinelt, Eva Tardos, Klaus Truemper, Yoshiko Wakabayashi, and Zaw Win. We mention at this point that the technique of applying the ellipsoid method to combinatorial optimization problems was also discovered by R. M. Karp, С. H. Papadimitriou, M. W. Padberg, and M. R. Rao.
We have worked on this book over a long period at various institutions. We acknowledge, in particular, the support of the joint research project of the German Research Association (DFG) and the Hungarian Academy of Sciences (MTA), the Universities of Amsterdam, Augsburg, Bonn, Szeged, and Tilburg, Cornell University (Ithaca), E5tv6s Lorand University (Budapest), and the Mathematical Centre (Amsterdam).
Our special thanks are due to Frau Theodora Konnerth for the efficient and careful typing and patient retyping of the text in TEX.