 | Du D. Design and analysis of approximation algorithms / Ding-Zhu Du, Ker-I Ko, Xiaodong Hu. - New York: Springer, 2012. - xi, 440 p. - (Springer optimization and its applications; vol.62). - Bibliogr.: p.407-424. - Ind.: p.425-440. - ISBN 978-1-4614-1700-2; ISSN 1931-6828
|
Preface ......................................................... v
1 Introduction ................................................. 1
1.1 Open Sesame ............................................. 1
1.2 Design Techniques for Approximation Algorithms .......... 8
1.3 Heuristics Versus Approximation ........................ 13
1.4 Notions in Computational Complexity .................... 14
1.5 NP-Complete Problems ................................... 17
1.6 Performance Ratios ..................................... 23
Exercises ................................................... 28
Historical Notes ............................................ 33
2 Greedy Strategy ............................................. 35
2.1 Independent Systems .................................... 35
2.2 Matroids ............................................... 40
2.3 Quadrilateral Condition on Cost Functions .............. 43
2.4 Submodular Potential Functions ......................... 49
2.5 Applications ........................................... 59
2.6 Nonsubmodular Potential Functions ...................... 66
Exercises ................................................... 75
Historical Notes ............................................ 80
3 Restriction ................................................. 81
3.1 Steiner Trees and Spanning Trees ....................... 82
3.2 k-Restricted Steiner Trees ............................. 86
3.3 Greedy k-Restricted Steiner Trees ...................... 89
3.4 The Power of Minimum Spanning Trees ................... 102
3.5 Phylogenetic Tree Alignment ........................... 110
Exercises .................................................. 115
Historical Notes ........................................... 121
4 Partition .................................................. 123
4.1 Partition and Shifting ................................ 123
4.2 Boundary Area ......................................... 129
4.3 Multilayer Partition .................................. 136
4.4 Double Partition ...................................... 142
4.4.1 A Weighted Covering Problem .................... 142
4.4.2 A 2-Approximation for WDS-UDG on a Small Cell .. 146
4.4.3 A 6-Approximation for WDS-UDG on a Large Cell .. 151
4.4.4 A (6 + ε)-Approximation for WDS-UDG ............ 155
4.5 Tree Partition ........................................ 157
Exercises .................................................. 160
Historical Notes ........................................... 164
5 Guillotine Cut ............................................. 165
5.1 Rectangular Partition ................................. 165
5.2 1-Guillotine Cut ...................................... 170
5.3 m-Guillotine Cut ...................................... 175
5.4 Portals ............................................... 184
5.5 Quadtree Partition and Patching ....................... 191
5.6 Two-Stage Portals ..................................... 201
Exercises .................................................. 205
Historical Notes ........................................... 208
6 Relaxation ................................................. 211
6.1 Directed Hamiltonian Cycles and Superstrings .......... 211
6.2 Two-Stage Greedy Approximations ....................... 219
6.3 Conected Dominating Sets in Unit Disk Graphs .......... 223
6.4 Strongly Connected Dominating Sets in Digraphs ........ 228
6.5 Multicast Routing in Optical Networks ................. 235
6.6 A Remark on Relaxation Versus Restriction ............. 238
Exercises .................................................. 240
Historical Notes ........................................... 243
7 Linear Programming ......................................... 245
7.1 Basic Properties of Linear Programming ................ 245
7.2 Simplex Method ........................................ 252
7.3 Combinatorial Rounding ................................ 259
7.4 Pipage Rounding ....................................... 267
7.5 Iterated Rounding ..................................... 272
7.6 Random Rounding ....................................... 280
Exercises .................................................. 289
Historical Notes ........................................... 295
8 Primal-Dual Schema and Local Ratio ......................... 297
8.1 Duality Theory and Primal-Dual Schema ................. 297
8.2 General Cover ......................................... 303
8.3 Network Design ........................................ 310
8.4 Local Ratio ........................................... 315
8.5 More on Equivalence ................................... 325
Exercises .................................................. 332
Historical Notes ........................................... 336
9 Semidefinite Programming ................................... 339
9.1 Spectrahedra .......................................... 339
9.2 Semidefinite Programming .............................. 341
9.3 Hyperplane Rounding ................................... 345
9.4 Rotation of Vectors ................................... 352
9.5 Multivariate Normal Rounding .......................... 358
Exercises .................................................. 363
Historical Notes ........................................... 369
10 Inapproximability .......................................... 371
10.1 Many-One Reductions with Gap .......................... 371
10.2 Gap Amplification and Preservation .................... 376
10.3 APX-Completeness ...................................... 380
10.4 PCP Theorem ........................................... 388
10.5 (ρ ln n)-Inapproximability ............................ 391
10.6 nc-Inapproximability .................................. 396
Exercises .................................................. 399
Historical Notes ........................................... 405
Bibliography .................................................. 407
Index ......................................................... 425
|
|
