Skip to main content
main-content

Über dieses Buch

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. NemirovskiI. 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.

Inhaltsverzeichnis

Frontmatter

Chapter 0. Mathematical Preliminaries

Abstract
This chapter summarizes mathematical background material from linear algebra, linear programming, and graph theory used in this book. We expect the reader to be familiar with the concepts treated here. We do not recommend to go thoroughly through all the definitions and results listed in the sequel — they are mainly meant for reference.
Martin Grötschel, László Lovász, Alexander Schrijver

Chapter 1. Complexity, Oracles, and Numerical Computation

Abstract
This chapter is still of a preliminary nature. It contains some basic notions of complexity theory and outlines some well-known algorithms. In addition, less standard concepts and results are described. Among others, we treat oracle algorithms, encoding lengths, and approximation framework in which algorithms are designed and aand computation of numbers, and we analyse the running time of Gaussian elimination and related procedures. The notions introduced in this chapter constitute thenalysed in this book. We intend to stay on a more or less informal level; nevertheless, all notions introduced here can be made completely precise — see for instance Aho, Hopcroft and Ullman (1974), Garey and Johnson (1979).
Martin Grötschel, László Lovász, Alexander Schrijver

Chapter 2. Algorithmic Aspects of Convex Sets: Formulation of the Problems

Abstract
Convex sets and convex functions are typical objects of study in mathematical programming, convex analysis, and related areas. Here are some key questions one encounters frequently:
  • Given a point y and a set K, is y a member of K, i. e., is y contained in K ?
  • If y is not a member of K, find a hyperplane separating y from K.
  • Given a linear inequality, is it valid for each vector in K ?
  • Given a linear function, find a point maximizing (or minimizing) the function on K.
  • Given a convex function, find its minimum.
Martin Grötschel, László Lovász, Alexander Schrijver

Chapter 3. The Ellipsoid Method

Abstract
In 1979 a note of L. G. Khachiyan indicated how an algorithm, the so-called ellipsoid method, originally devised for nonlinear nondifferentiable optimization, can be modified in order to check the feasibility of a system of linear inequalities in polynomial time. This result caused great excitement in the world of mathematical programming since it implies the polynomial time solvability of linear programming problems.
Martin Grötschel, László Lovász, Alexander Schrijver

Chapter 4. Algorithms for Convex Bodies

Abstract
We shall now exploit the ellipsoid method (the central-cut and the shallow-cut version) described in Chapter 3. In Sections 4.2, 4.3, and 4.4 we study the algorithmic relations between problems (2.1.10),..., (2.1.14), and we will prove that — under certain assumptions — these problems are equivalent with respect to polynomial time solvability. Section 4.5 serves to show that these assumptions cannot be weakened. In Section 4.6 we investigate various other basic questions of convex geometry from an algorithmic point of view and prove algorithmic analogues of some well-known theorems. Finally, in Section 4.7 we discuss to what extent algorithmic properties of convex bodies are preserved when they are subjected to operations like sum, intersection etc.
Martin Grötschel, László Lovász, Alexander Schrijver

Chapter 5. Diophantine Approximation and Basis Reduction

Abstract
As mentioned in Chapter 1, combinatorial optimization problems can usually be formulated as linear programs with integrality constraints. The geometric notion reflecting the main issues in linear programming is convexity, and we have discussed the main algorithmic problems on convex sets in the previous chapters. It turns out that it is also useful to formulate integrality constraints in a geometric way. This leads us to “lattices of points”. Such lattices have been studied (mostly from a nonalgorithmic point of view) in the “geometry of numbers”; their main application has been the theory of simultaneous diophantine approximation, i. e., the problem of approximating a set of real numbers by rational numbers with a common small denominator. We offer an algorithmic study of lattices and diophantine approximation.
Martin Grötschel, László Lovász, Alexander Schrijver

Chapter 6. Rational Polyhedra

Abstract
In most combinatorial (and real world) applications the convex sets one encounters are polyhedra. Often these polyhedra have “simple” vertices and facets. It turns out that the knowledge of such additional information on the convex sets in question extends the power of the ellipsoid method considerably. In particular, optimum solutions can be calculated exactly, boundedness and full-dimensionality assumptions can be dropped, and dual solutions can be obtained. In the case of explicitly given linear programs this was the main contribution of Khachiyan to the ellipsoid method. If the linear programs are given by some oracle — which is often the case in combinatorial optimization — then these additional goals can still be achieved, albeit with more involved techniques. In particular, we have to make use of the simultaneous diophantine approximation algorithm described in Chapter 5.
Martin Grötschel, László Lovász, Alexander Schrijver

Chapter 7. Combinatorial Optimization: Some Basic Examples

Abstract
In the remaining part of this book we apply the methods developed in the first part to combinatorial optimization. In this chapter we give some illuminating examples to explain the basic techniques of deriving polynomial time algorithms for combinatorial optimization problems. These techniques are based on combining the ellipsoid method and basis reduction with results from the field called “polyhedral combinatorics”, where combinatorial optimization problems are formulated as linear programs. Chapter 8 contains a comprehensive survey of combinatorial problems to which these methods apply. Finally, in the last two chapters we discuss some more advanced examples in greater detail.
Martin Grötschel, László Lovász, Alexander Schrijver

Chapter 8. Combinatorial Optimization: A Tour d’Horizon

Abstract
In Chapter 7 we have introduced several basic combinatorial optimization problems, and we have shown in detail how the ellipsoid method and basis reduction together with polyhedral information about these problems can be used to design polynomial time algorithms. In this chapter we give an overview about combinatorial optimization problems that are solvable in polynomial time. We also survey important theorems that provide polyhedral descriptions of the polytopes associated with these problems. We indicate how these results can be employed to derive polynomial time algorithms based on the ellipsoid method and basis reduction. The results of this chapter are presented in a condensed form, to cover as much material as possible.
Martin Grötschel, László Lovász, Alexander Schrijver

Chapter 9. Stable Sets in Graphs

Abstract
In this chapter we survey the results of the polyhedral approach to a particular NP-hard combinatorial optimization problem, the stable set problem in graphs. (Alternative names for this problem used in the literature are vertex packing, or coclique, or independent set problem.) Our basic technique will be to look for various classes of inequalities valid for the stable set polytope, and then develop polynomial time algorithms to check if a given vector satisfies all these constraints. Such an algorithm solves a relaxation of the stable set problem in polynomial time, i. e., provides an upper bound for the maximum weight of a stable set. If certain graphs have the property that every facet of the stable set polytope occurs in the given family of valid inequalities, then, for these graphs, the stable set problem can be solved in polynomial time. It turns out that there are very interesting classes of graphs which are in fact characterized by such a condition, most notably the class of perfect graphs. Using this approach, we shall develop a polynomial time algorithm for the stable set problem for perfect graphs. So far no purely combinatorial algorithm has been found to solve this problem in polynomial time.
Martin Grötschel, László Lovász, Alexander Schrijver

Chapter 10. Submodular Functions

Abstract
The concept of a submodular function in discrete optimization appears to be in several respects analogous to that of a convex function in continuous optimization. In many combinatorial theorems and problems, submodularity is involved, in one form or another, and submodularity often plays an essential role in a proof or an algorithm. Moreover, analogous to the fast methods for convex function minimization, it turns out that submodular functions can also be minimized fast, viz. in polynomial time. However, the only method known for this is, as yet, the ellipsoid method.
Martin Grötschel, László Lovász, Alexander Schrijver

Backmatter

Weitere Informationen