Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability PropertiesSpringer Science & Business Media, 09.11.1999 - 524 Seiten N COMPUTER applications we are used to live with approximation. Var I ious notions of approximation appear, in fact, in many circumstances. One notable example is the type of approximation that arises in numer ical analysis or in computational geometry from the fact that we cannot perform computations with arbitrary precision and we have to truncate the representation of real numbers. In other cases, we use to approximate com plex mathematical objects by simpler ones: for example, we sometimes represent non-linear functions by means of piecewise linear ones. The need to solve difficult optimization problems is another reason that forces us to deal with approximation. In particular, when a problem is computationally hard (i. e. , the only way we know to solve it is by making use of an algorithm that runs in exponential time), it may be practically unfeasible to try to compute the exact solution, because it might require months or years of machine time, even with the help of powerful parallel computers. In such cases, we may decide to restrict ourselves to compute a solution that, though not being an optimal one, nevertheless is close to the optimum and may be determined in polynomial time. We call this type of solution an approximate solution and the corresponding algorithm a polynomial-time approximation algorithm. Most combinatorial optimization problems of great practical relevance are, indeed, computationally intractable in the above sense. In formal terms, they are classified as Np-hard optimization problems. |
Inhalt
The Complexity of Optimization Problems | 1 |
11 Analysis of algorithms and complexity of problems | 2 |
111 Complexity analysis of computer programs | 3 |
112 Upper and lower bounds on the complexity of problems | 8 |
12 Complexity classes of decision problems | 9 |
121 The class NP | 12 |
13 Reducibility among problems | 17 |
132 NP complete problems | 21 |
62 Oracles | 188 |
621 Oracle Turing machines | 189 |
63 The PCP model | 190 |
632 Probabilistic Turing machines | 191 |
633 Verifiers and PCP | 193 |
634 A different view of NP | 194 |
64 Using PCP to prove non approximability results | 195 |
641 The maximum satisfiability problem | 196 |
14 Complexity of optimization problems | 22 |
142 PO and NPO problems | 26 |
143 NPhard optimization problems | 29 |
144 Optimization problems and evaluation problems | 31 |
15 Exercises | 33 |
16 Bibliographical notes | 36 |
Design Techniques for Approximation Algorithms | 39 |
21 The greedy method | 40 |
211 Greedy algorithm for the knapsack problem | 41 |
212 Greedy algorithm for the independent set problem | 43 |
213 Greedy algorithm for the salesperson problem | 47 |
22 Sequential algorithms for partitioning problems | 50 |
221 Scheduling jobs on identical machines | 51 |
222 Sequential algorithms for bin packing | 54 |
223 Sequential algorithms for the graph coloring problem | 58 |
23 Local search | 61 |
231 Local search algorithms for the cut problem | 62 |
232 Local search algorithms for the salesperson problem | 64 |
24 Linear programming based algorithms | 65 |
241 Rounding the solution of a linear program | 66 |
242 Primaldual algorithms | 67 |
25 Dynamic programming | 69 |
26 Randomized algorithms | 74 |
27 Approaches to the approximate solution of problems | 76 |
chapter 5 | 77 |
chapter 10 | 78 |
275 Final remarks | 79 |
29 Bibliographical notes | 83 |
Approximation Classes | 87 |
31 Approximate solutions with guaranteed performance | 88 |
312 Relative approximation | 90 |
313 Approximability and nonapproximability of TSP | 94 |
The gap technique | 100 |
32 Polynomialtime approximation schemes | 102 |
321 The class PTAS | 105 |
322 APX versus PTAS | 110 |
33 Fully polynomialtime approximation schemes | 111 |
332 The variable partitioning technique | 112 |
333 Negative results for the class FPTAS | 113 |
334 Strong NPcompleteness and pseudopolynomiality | 114 |
34 Exercises | 116 |
35 Bibliographical notes | 119 |
InputDependent and Asymptotic Approximation | 123 |
41 Between APX and NPO | 124 |
412 Approximating the graph coloring problem | 127 |
42 Between APX and PTAS | 139 |
422 Approximating the bin packing problem | 143 |
43 Exercises | 148 |
44 Bibliographical notes | 150 |
Approximation through Randomization | 153 |
51 Randomized algorithms for weighted vertex cover | 154 |
52 Randomized algorithms for weighted satisfiability | 157 |
522 A 43 approximation randomized algorithm | 160 |
53 Algorithms based on semidefinite programming | 162 |
531 Improved algorithms for weighted 2 satisfiability | 167 |
54 The method of the conditional probabilities | 168 |
55 Exercises | 171 |
56 Bibliographical notes | 173 |
NP PCP and Nonapproximability Results | 175 |
612 Deterministic Turing machines | 178 |
613 Nondeterministic Turing machines | 180 |
614 Time and space complexity | 181 |
615 NPcompleteness and CookLevin theorem | 184 |
642 The maximum clique problem | 198 |
65 Exercises | 200 |
66 Bibliographical notes | 204 |
The PCP theorem | 207 |
71 Transparent long proofs | 208 |
711 Linear functions | 210 |
712 Arithmetization | 214 |
713 The first PCP result | 218 |
72 Almost transparent short proofs | 221 |
721 Lowdegree polynomials | 222 |
722 Arithmetization revisited | 231 |
723 The second PCP result | 238 |
73 The final proof | 239 |
731 Normal form verifiers | 241 |
732 The composition lemma | 245 |
74 Exercises | 248 |
Approximation Preserving Reductions | 253 |
81 The World of NPO Problems | 254 |
82 AP reducibility | 256 |
821 Complete problems | 261 |
831 Other NPOcomplete problems | 265 |
84 APXcompleteness | 266 |
841 Other APXcomplete problems | 270 |
85 Exercises | 281 |
86 Bibliographical notes | 283 |
Probabilistic analysis of approximation algorithms | 287 |
91 Introduction | 288 |
911 Goals of probabilistic analysis | 289 |
92 Techniques for the probabilistic analysis of algorithms | 291 |
922 The first and the second moment methods | 293 |
923 Convergence of random variables | 294 |
93 Probabilistic analysis and multiprocessor scheduling | 296 |
94 Probabilistic analysis and bin packing | 298 |
95 Probabilistic analysis and maximum clique | 302 |
96 Probabilistic analysis and graph coloring | 311 |
97 Probabilistic analysis and Euclidean TSP | 312 |
98 Exercises | 316 |
99 Bibliographical notes | 318 |
Heuristic methods | 321 |
101 Types of heuristics | 322 |
102 Construction heuristics | 325 |
103 Local search heuristics | 329 |
1031 Fixeddepth local search heuristics | 330 |
1032 Variabledepth local search heuristics | 336 |
104 Heuristics based on local search | 341 |
1042 Genetic algorithms | 344 |
1043 Tabu search | 347 |
105 Exercises | 349 |
106 Bibliographical notes | 350 |
Mathematical preliminaries | 353 |
A11 Sequences tuples and matrices | 354 |
A2 Functions and relations | 355 |
A3 Graphs | 356 |
A4 Strings and languages | 357 |
A6 Probability | 358 |
A61 Random variables | 359 |
A7 Linear programming | 361 |
A8 Two famous formulas | 365 |
A List of NP Optimization Problems | 367 |
Bibliography | 471 |
515 | |
Andere Ausgaben - Alle anzeigen
Häufige Begriffe und Wortgruppen
3-SATISFIABILITY Admits a PTAS approximate solution approximation algorithm approximation preserving APX-complete Arora Bibliographical notes Boolean formula bound cities clauses computation constant corresponding decision problem defined definition denotes disjoint edge example Exercise exists feasible solution Fit Decreasing FPTAS function f Garey and Johnson Given an instance GRAPH COLORING graph G greedy Halldórsson heuristics inequality input Lemma length linear program maximization MAXIMUM 3-SATISFIABILITY MAXIMUM CLIQUE MAXIMUM INDEPENDENT SET MAXIMUM WEIGHTED minimize MINIMUM BIN PACKING MINIMUM TRAVELING SALESPERSON nodes nondeterministic NP-hard NPO problems obtain optimal solution optimization problems oracle P₁ pair partition path PCP theorem performance ratio planar graphs polynomial polynomial-time approximation scheme prob PROBABILISTIC ANALYSIS probability proof prove random variable randomized algorithm schedule sequence solution found string subgraph subset technique tour triangle inequality truth assignment Turing machine V₁ variation verifier vertices WEIGHTED SATISFIABILITY Yannakakis
Beliebte Passagen
Seite 477 - Fourth Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science 955, Springer, Berlin, 86-97, 1995.
Seite 493 - DS Hochbaum and DB Shmoys. A polynomial approximation scheme for machine scheduling on uniform processors: using the dual approximation approach.
Seite 491 - School of Information Science, Japan Advanced Institute of Science and Technology, Hokuriku, Tatsunokuchi, Ishikawa 923-12, Japan \ Department of Electrical and Computer Engineering.
Verweise auf dieses Buch
Introduction To Algorithms Thomas H Cormen,Charles E Leiserson,Ronald L Rivest,Clifford Stein Eingeschränkte Leseprobe - 2001 |