Annotated bibliographies in combinatorial optimization

Front Cover
Wiley, Aug 28, 1997 - Mathematics - 495 pages
0 Reviews
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.

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Hardness of Approximation
13
Polyhedral Combinatorics
31
BranchandCut Algorithms
45
Matroids and Submodular Functions
65
Perfect Ideal and Balanced Matrices
81
Advances in Linear Optimization
97
Decomposition and Column Generation
115
Randomized Algorithms
143
MaxCut Problem
241
Location Problems
261
Flows and Paths
283
Network Design
311
Network Connectivity
335
Linear Assignment
355
Quadratic and ThreeDimensional Assignments
373
Cutting and Packing
393

Local Search
163
Sequencing and Scheduling
181
The Traveling Salesman Problem
199
Vehicle Routing
223
Set Covering Problem
415
Combinatorial Topics in VLSI Design
429
Computational Molecular Biology
445
Copyright