Surveys in Combinatorial Optimization (Mathematics Studies)
By Silvano Martello, etc.
* Publisher: Elsevier Science Ltd
* Number Of Pages: 394
* Publication Date: 1987-01
* ISBN-10 / ASIN: 0444701362
* ISBN-13 / EAN: 9780444701367
PREFACE
Ever since the field of Mathematical Programming was born with the discovery
of the Simplex method by G.B. Dantzig in the late 1940s, researchers have
devoted considerable attention to optimization problems in which the variables
are constrained to take only integer values, or values from a finite or discrete
set of numbers.
After the first significant contributions of R.E. Gomory t o the field of Integer
Programming, discrete optimization problems were to attract growing interest,
partly because of the fact that a large number of practical applications of Operations
Research techniques involved integrality constraints, and partly because
of the theoretical challenge.
During the same period, Graph Theory had been developing, providing a natural
and effective conceptual framework for expressing and sometimes solving combinatorial
problems commonly encountered in applications, thus giving rise to
network flow theory, matroid theory and complexity theory.
What is nowadays referred t o as Combinatorial Optimization therefore 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 is an attempt to provide a synthetic overview of a number
of important directions in which Combinatorial Optimization is currently developing,
in the for& of a collection of survey papers providing detailed accounts of
recent progress over the past few years.
A number of these papers focus more specifically on theoretical aspects
and fundamental tools of Combinatorial Optimization: ((Boolean Programming))
and ((Probabilistic Analysis of Algorithms)). From the computational point of
view, a good account of recent work on the use of vector processing and parallel
computers for implementing algorithms will be found in the paper on ((Parallel
Computer Models and Combinatorial 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: we refer, in particular,
to the papers on ((The Linear Assignment Problem >), ((The Quadratic
Assignment Problem)), ((The Knapsack Problem)) and ((The Steiner Problem in
Graphs)).
Besides these, it also seemed important that the wide applicability of the
techniques and algorithmic tools developed in the field of Combinatorial Optimi
zation be illustrated with a number of more complicated models chosen for their
technical, industrial or economic importance. Accordingly, the reader will find
a number of applications oriented papers devoted to combinatorial problems
arising in such practical contexts as: communication networks (((Network Synthesis
and Dynamic Network Optimization))), location and routing (((Single Facility
Location Problems on Networks)) and ((The Vehicle Routing Problem))), manufacturing
and planning in production systems (((Scheduling Problems))).
All the survey papers included herein have been written by well-known specialists
in the field, with particular emphasis on pedagogical quality (in this respect,
special mention should be given to the bibliography which contains almost
1000 titles) and, as far as possible, completeness.
The Editors wish to thank the participants of the School on Combinatorial
Optimization for their valuable comments and criticisms on preliminary versions
of the papers. The financial support of the Federal University of Rio de Janeiro,
the National Research Council of Italy and the ficole des Hautes etudes Commerciales
de MontrCal is gratefully acknowledged.
We hope that this volume will be considered as a milestone in the rich and
fast evolving field of Combinatorial Optimization.
Silvano Martello
Gilbert Laporte
Michel Minoux
Celso Ribeiro
http://ifile.it/l6bthw3/0444701362_combinatorial_optimization.rar
