Design and Analysis of Approximation Algorithms
Author(s):        Ding-Zhu Du, Ker-I Ko, Xiaodong Hu
Series:        Springer Optimization and Its Applications volume 62       
Publisher:        Springer
Pub Year:        2011       
Edition: 2012
Language:        English       
Pages:        450
ISBN:        1461417007, 9781461417002


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.
Table of contents :
Cover......Page 1
Title......Page 4
Copyright......Page 5
Preface......Page 6
Contents......Page 10
1.1 Open Sesame......Page 14
1.2 Design Techniques for Approximation Algorithms......Page 21
1.3 Heuristics Versus Approximation......Page 26
1.4 Notions in Computational Complexity......Page 27
1.5 NP-Complete Problems......Page 30
1.6 Performance Ratios......Page 36
Exercises......Page 41
Historical Notes......Page 46
2.1 Independent Systems......Page 47
2.2 Matroids......Page 52
2.3 Quadrilateral Condition on Cost Functions......Page 55
2.4 Submodular Potential Functions......Page 61
2.5 Applications......Page 71
2.6 Nonsubmodular Potential Functions......Page 78
Exercises......Page 87
Historical Notes......Page 92
3 Restriction......Page 93
3.1 Steiner Trees and Spanning Trees......Page 94
3.2 k-Restricted Steiner Trees......Page 98
3.3 Greedy k-Restricted Steiner Trees......Page 101
3.4 The Power of Minimum Spanning Trees......Page 114
3.5 Phylogenetic Tree Alignment......Page 122
Exercises......Page 127
Historical Notes......Page 133
4.1 Partition and Shifting......Page 135
4.2 Boundary Area......Page 141
4.3 Multilayer Partition......Page 148
4.4.1 A Weighted Covering Problem......Page 154
4.4.2 A 2-Approximation for WDS-UDG on a Small Cell......Page 158
4.4.3 A 6-Approximation for WDS-UDG on a Large Cell......Page 163
4.4.4 A (6 + ε)-Approximation for WDS-UDG......Page 167
4.5 Tree Partition......Page 169
Exercises......Page 172
Historical Notes......Page 176
5.1 Rectangular Partition......Page 177
5.2 1-Guillotine Cut......Page 182
5.3 m-Guillotine Cut......Page 187
5.4 Portals......Page 196
5.5 Quadtree Partition and Patching......Page 203
5.6 Two-Stage Portals......Page 213
Exercises......Page 217
Historical Notes......Page 220
6.1 Directed Hamiltonian Cycles and Superstrings......Page 222
6.2 Two-Stage Greedy Approximations......Page 230
6.3 Connected Dominating Sets in Unit Disk Graphs......Page 234
6.4 Strongly Connected Dominating Sets in Digraphs......Page 239
6.5 Multicast Routing in Optical Networks......Page 246
6.6 A Remark on Relaxation versus Restriction......Page 249
Exercises......Page 251
Historical Notes......Page 254
7.1 Basic Properties of Linear Programming......Page 256
7.2 Simplex Method......Page 263
7.3 Combinatorial Rounding......Page 270
7.4 Pipage Rounding......Page 278
7.5 Iterated Rounding......Page 283
7.6 Random Rounding......Page 291
Exercises......Page 300
Historical Notes......Page 306
8.1 Duality Theory and Primal-Dual Schema......Page 308
8.2 General Cover......Page 314
8.3 Network Design......Page 321
8.4 Local Ratio......Page 326
8.5 More on Equivalence......Page 336
Exercises......Page 343
Historical Notes......Page 347
9.1 Spectrahedra......Page 349
9.2 Semidefinite Programming......Page 351
9.3 Hyperplane Rounding......Page 355
9.4 Rotation of Vectors......Page 362
9.5 Multivariate Normal Rounding......Page 368
Exercises......Page 373
Historical Notes......Page 379
10.1 Many–One Reductions with Gap......Page 381
10.2 Gap Amplification and Preservation......Page 386
10.3 APX-Completeness......Page 390
10.4 PCP Theorem......Page 398
10.5 (ρ ln n)-Inapproximability......Page 401
10.6 nc-Inapproximability......Page 406
Exercises......Page 409
Historical Notes......Page 415
Bibliography......Page 417
Index......Page 435