zbMATH — the first resource for mathematics

Design and analysis of approximation algorithms. (English) Zbl 1237.68009
Springer Optimization and Its Applications 62. New York, NY: Springer (ISBN 978-1-4614-1700-2/hbk; 978-1-4614-1701-9/ebook). xi, 440 p. (2012).
The book under review has been published as part of Springer’s Optimization and Its Application series. It contains a large amount of precisely selected topics covering various aspects and design techniques related to approximation algorithms. It provides an intensive study of the main methods used in the field, with abundant applications following the discussion of each method. It is organized according to design methods instead of application problems. Thus, one can study approximation algorithms of the same nature together, and learn about the design techniques in a more unified way. It has been intended as a textbook for a graduate course in theoretical computer science. However, thanks to the rich set of results covered it can also be used as a reference book for postgraduate students and researchers in the area of design and analysis of algorithms. It also serves as a reference for established researchers by providing efficient tools for various applied areas like applied mathematics, engineering, medicine, economics, and other sciences.
This book has grown out of lecture notes used by the authors at their universities. Besides being extremely useful to those who are interested in design and analysis techniques, graph connectivities, matroid optimization and submodular functions, the book is also of great interest to anyone interested in general combinatorial optimization theory. It is written in a highly scientific language and it is extraordinarily beneficial reading for graduates and researchers in mathematics and in theoretical computer science who focus on algorithms for solving optimization problems and also study applications involving such problems.

68-02 Research exposition (monographs, survey articles) pertaining to computer science
68W25 Approximation algorithms
68W40 Analysis of algorithms
90C90 Applications of mathematical programming
Full Text: DOI