scientific article; zbMATH DE number 193499

From MaRDI portal
Publication:4040299





The volume presents the general theory and algorithms essential for nearly all parts of discrete optimization. After a short introduction the material starts in Chapter 2 with complexity theory, more precisely, with time complexity. Here the basic ideas of computability, worst-case analysis and the classes of decision problems P, NP and NP-complete are treated. The subsequent five chapters of the book are dedicated to the algorithmic categories delineated by complexity theory. In Chapters 3 and 4 the authors address time-polynomial procedures. Main topics here are matroids, time-polynomial algorithms in linear programming and their relations to polyhedra arising in combinatorial problems. Chapter 5 deals with partial enumeration procedures. The linear programming based methods are fully considered, along with Lagrangian dual ideas and Benders' decomposition. The alternative to enumeration, i.e. polyhedral description, is focused in Chapter 6. Here, the modern general theory of cutting methods is discussed along with an introduction to the specialized facetial techniques useful for specific problems. Chapter 7 contains nonexact, heuristic procedures. A general discussion of such algorithms is followed by the investigation of greedy, local search, and truncated exponential algorithms. Three appendices dedicated to fundamental results from linear programming, graph theory, convex sets, and polyhedra complete the book. The selection and presentation of the material which covers the main developments in the field of discrete optimization during the past quarter of the century are both nice. Algorithms are written in a computational format and illustrated throughout by examples. The list of references is not comprehensive in the sense of a literature review but reflects the essential papers concerning the given concepts, theorems and algorithms. The book will be very useful for students, instructors and researchers in the field.





Cited in
(92)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4040299)