This book is intended to be used as a textbook for graduate students
studying theoretical computer science. It can also be used as a
reference book for researchers in the area of design and analysis of
approximation algorithms. Design and Analysis of Approximation
Algorithms is a graduate course in theoretical computer science taught
widely in the universities, both in the United States and abroad. There
are, however, very few textbooks available for this course. Among those
available in the market, most books follow a problem-oriented format;
that is, they collected many important combinatorial optimization
problems and their approximation algorithms, and organized them based on
the types, or applications, of problems, such as geometric-type
problems, algebraic-type problems, etc. Such arrangement of materials is
perhaps convenient for a researcher to look for the problems and
algorithms related to his/her work, but is difficult for a student to
capture the ideas underlying the various algorithms. In the new book
proposed here, we follow a more structured, technique-oriented
presentation. We organize approximation algorithms into different
chapters, based on the design techniques for the algorithms, so that the
reader can study approximation algorithms of the same nature together.
It helps the reader to better understand the design and analysis
techniques for approximation algorithms, and also helps the teacher to
present the ideas and techniques of approximation algorithms in a more
unified way.
