Approximation Algorithms

Front Cover
Springer Science & Business Media, Dec 5, 2002 - Computers - 380 pages
4 Reviews
Reviews aren't verified, but Google checks for and removes fake content when it's identified
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
CXXII
172
CXXIII
174
CXXIV
175
CXXV
176
CXXVI
178
CXXVII
179
CXXIX
180
CXXX
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
CVIII
148
CIX
151
CX
153
CXI
154
CXIII
156
CXIV
159
CXV
162
CXVI
166
CXVII
167
CXIX
169
CXX
170
CXXI
171
CXXXII
184
CXXXIII
185
CXXXIV
186
CXXXV
189
CXXXVI
190
CXXXVII
191
CXL
192
CXLI
193
CXLII
194
CXLIII
196
CXLIV
197
CXLVI
198
CXLVII
203
CXLVIII
206
CXLIX
211
CL
212
CLII
216
CLIII
218
CLIV
220
CLV
223
CLVI
230
CLVII
231
CLVIII
232
CLIX
233
CLX
234
CLXI
235
CLXII
237
CLXIV
238
CLXV
241
CLXVI
242
CLXVIII
243
CLXIX
246
CLXX
248
CLXXII
249
CLXXIV
250
CLXXV
253
CLXXVI
255
CLXXVIII
257
CLXXIX
258
CLXXX
260
CLXXXI
263
CLXXXII
265
CLXXXIII
268
CLXXXIV
273
CLXXXV
274
CLXXXVI
276
CLXXXVII
278
CLXXXVIII
280
CLXXXIX
284
CXC
288
CXCI
292
CXCII
294
CXCIII
295
CXCIV
297
CXCV
298
CXCVI
300
CXCVII
302
CXCVIII
306
CC
309
CCI
311
CCII
313
CCIII
316
CCIV
318
CCV
322
CCVII
324
CCVIII
325
CCIX
326
CCX
329
CCXI
332
CCXII
334
CCXIV
336
CCXV
338
CCXVI
343
CCXVII
344
CCXVIII
345
CCXIX
346
CCXX
348
CCXXII
349
CCXXIII
352
CCXXIV
353
CCXXVI
354
CCXXVII
355
CCXXIX
357
CCXXX
373
CCXXXI
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.

Bibliographic information