| Book Name: | Design and Analysis of Approximation Algorithms |
| Category: | Algorithms |
| Free Download: | Available |
Design and Analysis of Approximation Algorithms
Book Description:
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 approximation algorithm design and analysis. Approximation Algorithm Design and Analysis is an undergraduate degree program in theoretical computer science taught extensively at universities, both in the United States and abroad. However, there are very few textbooks available for this course. Of those available on the market, most books follow a problem-oriented format; that is, they have collected many important combinatorial optimization problems and their approximation algorithms and organized them according to types of problems or applications, such as geometric problems, algebraic problems, and so on. Such an arrangement of materials may be convenient for a researcher to search for problems and algorithms related to his or her work, but it is difficult for a student to grasp the ideas behind the various algorithms. In the new book proposed here, we follow a more structured and technique-oriented presentation. We organize the approximation algorithms in several chapters, based on the algorithm design techniques, so that the reader can study together the approximation algorithms of the same nature. It helps the reader to better understand the design and analysis techniques of approximation algorithms and also helps the teacher to present the ideas and techniques of approximation algorithms in a more unified way.
Table of contents :
Front Matter….Pages i-xi
Introduction….Pages 1-33
Greedy Strategy….Pages 35-80
Restriction….Pages 81-122
Partition….Pages 123-164
Guillotine Cut….Pages 165-209
Relaxation….Pages 211-244
Linear Programming….Pages 245-296
Primal-Dual Schema and Local Ratio….Pages 297-337
Semidefinite Programming….Pages 339-370
Inapproximability….Pages 371-406
Back Matter….Pages 407-440
Design and Analysis of Approximation Algorithms
Author(s): Ding-Zhu Du, Ker-I Ko, Xiaodong Hu (auth.)
Series: Springer Optimization and Its Applications 62
Publisher: Springer-Verlag New York, Year: 2012
ISBN: 1461417007,9781461417002
