Approximation Algorithms

Front Cover
Springer Science & Business Media, Dec 5, 2002 - Computers - 380 pages
4 Reviews
Although this may seem a paradox, all exact science is dominated by the idea of approximation. Bertrand Russell (1872-1970) Most natural optimization problems, including those arising in important application areas, are NP-hard. Therefore, under the widely believed con jecture that P -=/= NP, their exact solution is prohibitively time consuming. Charting the landscape of approximability of these problems, via polynomial time algorithms, therefore becomes a compelling subject of scientific inquiry in computer science and mathematics. This book presents the theory of ap proximation algorithms as it stands today. It is reasonable to expect the picture to change with time. This book is divided into three parts. In Part I we cover combinato rial algorithms for a number of important problems, using a wide variety of algorithm design techniques. The latter may give Part I a non-cohesive appearance. However, this is to be expected - nature is very rich, and we cannot expect a few tricks to help solve the diverse collection of NP-hard problems. Indeed, in this part, we have purposely refrained from tightly cat egorizing algorithmic techniques so as not to trivialize matters. Instead, we have attempted to capture, as accurately as possible, the individual character of each problem, and point out connections between problems and algorithms for solving them.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

I
1
II
2
III
3
V
5
VI
7
VII
10
VIII
15
IX
16
CXX
172
CXXI
174
CXXII
175
CXXIII
176
CXXIV
178
CXXV
179
CXXVII
180
CXXVIII
182

X
17
XI
19
XII
22
XIII
26
XIV
27
XVI
28
XVII
30
XVIII
31
XIX
32
XX
33
XXI
37
XXII
38
XXIV
40
XXV
44
XXVI
46
XXVII
47
XXIX
50
XXX
52
XXXI
53
XXXII
54
XXXIV
57
XXXV
60
XXXVII
61
XXXIX
64
XL
66
XLII
67
XLIII
68
XLIV
69
XLVI
71
XLVII
72
XLIX
73
L
74
LII
77
LIII
78
LIV
79
LVI
80
LVII
81
LIX
83
LXI
84
LXIII
87
LXIV
89
LXVI
93
LXVIII
97
LXIX
100
LXX
101
LXXI
103
LXXII
107
LXXIII
108
LXXV
111
LXXVI
112
LXXVIII
116
LXXIX
117
LXXX
118
LXXXII
119
LXXXIII
121
LXXXIV
122
LXXXV
123
LXXXVI
124
LXXXVIII
126
LXXXIX
128
XC
129
XCI
130
XCII
131
XCIV
133
XCV
135
XCVI
136
XCVII
138
XCVIII
139
C
140
CI
141
CII
142
CIII
143
CIV
144
CV
145
CVI
148
CVII
151
CVIII
153
CIX
154
CXI
156
CXII
159
CXIII
162
CXIV
166
CXV
167
CXVII
169
CXVIII
170
CXIX
171
CXXX
184
CXXXI
185
CXXXII
186
CXXXIII
189
CXXXIV
190
CXXXV
191
CXXXVIII
192
CXXXIX
193
CXL
194
CXLI
196
CXLII
197
CXLIV
198
CXLV
203
CXLVI
206
CXLVII
211
CXLVIII
212
CL
216
CLI
218
CLII
220
CLIII
223
CLIV
230
CLV
231
CLVI
232
CLVII
233
CLVIII
234
CLIX
235
CLX
237
CLXII
238
CLXIII
241
CLXIV
242
CLXVI
243
CLXVII
246
CLXVIII
248
CLXX
249
CLXXII
250
CLXXIII
253
CLXXIV
255
CLXXVI
257
CLXXVII
258
CLXXVIII
260
CLXXIX
263
CLXXX
265
CLXXXI
268
CLXXXII
273
CLXXXIII
274
CLXXXIV
276
CLXXXV
278
CLXXXVI
280
CLXXXVII
284
CLXXXVIII
288
CLXXXIX
292
CXC
294
CXCI
295
CXCII
297
CXCIII
298
CXCIV
300
CXCV
302
CXCVI
306
CXCVIII
309
CXCIX
311
CC
313
CCI
316
CCII
318
CCIII
322
CCV
324
CCVI
325
CCVII
326
CCVIII
329
CCIX
332
CCX
334
CCXII
336
CCXIII
338
CCXIV
343
CCXV
344
CCXVI
345
CCXVII
346
CCXVIII
348
CCXX
349
CCXXI
352
CCXXII
353
CCXXIV
354
CCXXV
355
CCXXVII
357
CCXXVIII
373
CCXXIX
377
Copyright

Other editions - View all

Common terms and phrases

Popular passages

Page 357 - F. Alizadeh. Interior point methods in semidefinite programming with applications to combinatorial optimization.
Page 359 - M. Charikar and S. Guha. Improved combinatorial algorithms for the facility location and k-median problems.
Page 362 - U. Feige, S. Goldwasser, L. Lovasz, S. Safra, and M. Szegedy. Approximating clique is almost NPcomplete. In Proc.
Page 358 - Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications.
Page 357 - Hochbaum, editor, Approximation Algorithms for NPHard Problems, pages 46-93. PWS Publishing, Boston, 1996.
Page 364 - DS Hochbaum. Approximation Algorithms for the Set Covering and Vertex Cover Problems.
Page 357 - S. Arora. Polynomial time approximation scheme for Euclidean TSP and other geometric problems. In Proc. 37th IEEE Annual Symposium on Foundations of Computer Science, pages 2-11, 1996. (Cited on p. 89) 11. S. Arora. Nearly linear time approximation scheme for Euclidean TSP and other geometric problems.
Page 363 - N. Garg, VV Vazirani, and M. Yannakakis. Multiway cuts in directed and node weighted graphs. In Proc.
Page 358 - M. Bern and P. Plassmann. The Steiner problem with edge lengths 1 and 2.

References to this book

All Book Search results »

Bibliographic information