Surveys in Combinatorial Optimization

What is nowadays referred to as ‘Combinatorial Optimization, derives from the combination and cross-fertilization of various research streams, all developed somewhat independently over the past two or three decades, such as Graph Theory, Integer Programming, Combinatorics and Discrete Mathematics. The present volume provides a synthetic overview of a number of important directions in which Combinatorial Optimization is currently developing, in the form of a collection of survey papers providing detailed accounts of recent progress. A number of these papers focus more specifically on theoretical aspects and fundamental tools of Combinatorial Optimization: Boolean Programming and Probabilistic Analysis of Algorithms. In addition, substantial space has been allocated to a number of well known problems, which have some relation with applications, but which are addressed here as prototypes of hard-to-solve combinatorial problems, and which, as such, have traditionally acted as stimulants for research in the field: the linear assignment problem, the quadratic assignment problem, the knapsack problem and the Steiner problem in graphs. Besides these, the wide applicability of the techniques and algorithmic tools developed in the field of Combinatorial Optimization is illustrated with a number of more complicated models chosen for their technical, industrial or economic importance. Accordingly, there are applications oriented papers devoted to a combinatorial problems arising in such practical contexts as communications networks, location, routing and manufacturing and planning in production systems.