Lectures on Proof Verification and Approximation Algorithms

Front Cover
Springer Science & Business Media, Feb 25, 1998 - Computers - 344 pages
During the last few years, we have seen quite spectacular progress in the area of approximation algorithms: for several fundamental optimization problems we now actually know matching upper and lower bounds for their approximability. This textbook-like tutorial is a coherent and essentially self-contained presentation of the enormous recent progress facilitated by the interplay between the theory of probabilistically checkable proofs and aproximation algorithms. The basic concepts, methods, and results are presented in a unified way to provide a smooth introduction for newcomers. These lectures are particularly useful for advanced courses or reading groups on the topic.
 

What people are saying - Write a review

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

Contents

II
5
IV
6
V
12
VI
16
VII
29
IX
30
X
32
XI
34
LI
198
LII
213
LIV
215
LV
217
LVI
221
LVII
225
LVIII
230
LIX
235

XII
37
XIII
41
XV
42
XVI
44
XVII
46
XVIII
53
XIX
55
XX
56
XXI
63
XXIV
66
XXV
69
XXVI
71
XXVII
73
XXVIII
77
XXIX
83
XXXI
85
XXXII
88
XXXIII
109
XXXIV
121
XXXV
134
XXXVI
141
XXXVII
157
XXXVIII
161
XLI
162
XLII
164
XLIII
166
XLIV
168
XLV
171
XLVI
179
XLVII
180
XLVIII
181
XLIX
189
L
192
LXI
236
LXII
239
LXIII
243
LXIV
249
LXVI
252
LXVII
255
LXVIII
256
LXIX
263
LXXI
267
LXXII
270
LXXIII
274
LXXIV
278
LXXV
285
LXXVI
289
LXXVII
293
LXXVIII
296
LXXIX
299
LXXXI
300
LXXXII
304
LXXXIII
308
LXXXIV
310
LXXXV
313
LXXXVII
314
LXXXVIII
316
LXXXIX
320
XC
321
XCI
322
XCII
325
XCIII
335
XCIV
337
XCV
343
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information