Skip to main content

Annotated Bibliographies in Combinatorial Optimization

Annotated Bibliographies in Combinatorial Optimization

Mauro Dell'Amico (Editor), Francesco Maffioli (Editor), Silvano Martello

ISBN: 978-0-470-86070-0

Sep 1997

512 pages

Select type: E-Book


Product not available for purchase


Wiley-Interscience Series in Discrete Mathematics and Optimization Advisory Editors Ronald L. Graham Jan Karel Lenstra Robert E. Tarjan Discrete Mathematics and Optimization involves the study of finite structures and is one of the fastest growing areas in mathematics today. The level and depth of recent advances in the area and the wide applicability of its evolving techniques point to the rapidity with which the field is moving and presage the ever-increasing interaction between it and computer science. The Series provides a broad coverage of discrete mathematics and optimization, ranging over such fields as combinatorics, graph theory, enumeration, mathematical programming and the analysis of algorithms, and including such topics as Ramsey theory, transversal theory, block designs, finite geometries, Polya theory, graph and matroid algorithms, network flows, polyhedral combinatorics and computational complexity. The Wiley-Interscience Series in Discrete Mathematics and Optimization will be a substantial part of the record in this extraordinary development. Recent titles in the Series: Local Search in Combinatorial Optimization Edited by Emile H. L. Aarts Philips Research Laboratories, Eindhoven and Eindhoven University of Technology, Eindhoven Jan Karel Lenstra Eindhoven University of Technology, Eindhoven and CWI Amsterdam In the past three decades local search has grown from a simple heuristic idea into a mature field of research in combinatorial optimization. Local search is still the method of choice for NP-hard problems as it provides a robust approach for obtaining high-quality solutions to problems of a realistic size in a reasonable time. This area of discrete mathematics is of great practical use and is attracting ever-increasing attention. The contributions to this book cover local search and its variants from both a theoretical and practical point of view, each with a chapter written by leading authorities on that particular aspect. Chapters 1 to 7 deal with the theory of local search and describe the principal search strategies such as simulated annealing, tabu search, genetic algorithms and neural networks. The remaining chapters present a wealth of results on applications of local search to problems in management science and engineering, including the traveling salesman problem, vehicle routing, machine scheduling, VLSI design and code design. This book is an important reference volume and an invaluable source of inspiration for advanced students and researchers in discrete mathematics, computer science, operations research, industrial engineering and management science.
Part I: General Methodologies. Complexity and Approximability;
Polyhedral Combinatorics;
Branch-and-Cut Algorithms;
Matroids and Submodular Functions;
Advances in Linear Programming;
Decomposition and Column Generation;
Stochastic Integer Programming;
Randomized Algorithms;
Local Search;
Graphs and Matrices;
Part II: Specific Topics and Applications. Sequencing and Scheduling;
Travelling Salesman Problem;
Max Cut;
Location Problems;
Network Design;
Flows and Paths;
Quadratic and 3-Dimensional Assignments;
Linear Assignment;
Vehicle Routing;
Cutting and Packing;
Combinatorial Topics in VLSI Design;
Applications in Computational Biology.