Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties - Softcover

Inhaltsangabe

1 The Complexity of Optimization Problems.- 1.1 Analysis of algorithms and complexity of problems.- 1.1.1 Complexity analysis of computer programs.- 1.1.2 Upper and lower bounds on the complexity of problems.- 1.2 Complexity classes of decision problems.- 1.2.1 The class NP.- 1.3 Reducibility among problems.- 1.3.1 Karp and Turing reducibility.- 1.3.2 NP-complete problems.- 1.4 Complexity of optimization problems.- 1.4.1 Optimization problems.- 1.4.2 PO and NPO problems.- 1.4.3 NP-hard optimization problems.- 1.4.4 Optimization problems and evaluation problems.- 1.5 Exercises.- 1.6 Bibliographical notes.- 2 Design Techniques for Approximation Algorithms.- 2.1 The greedy method.- 2.1.1 Greedy algorithm for the knapsack problem.- 2.1.2 Greedy algorithm for the independent set problem.- 2.1.3 Greedy algorithm for the salesperson problem.- 2.2 Sequential algorithms for partitioning problems.- 2.2.1 Scheduling jobs on identical machines.- 2.2.2 Sequential algorithms for bin packing.- 2.2.3 Sequential algorithms for the graph coloring problem.- 2.3 Local search.- 2.3.1 Local search algorithms for the cut problem.- 2.3.2 Local search algorithms for the salesperson problem.- 2.4 Linear programming based algorithms.- 2.4.1 Rounding the solution of a linear program.- 2.4.2 Primal-dual algorithms.- 2.5 Dynamic programming.- 2.6 Randomized algorithms.- 2.7 Approaches to the approximate solution of problems.- 2.7.1 Performance guarantee: chapters 3 and 4.- 2.7.2 Randomized algorithms: chapter 5.- 2.7.3 Probabilistic analysis: chapter 9.- 2.7.4 Heuristics: chapter 10.- 2.7.5 Final remarks.- 2.8 Exercises.- 2.9 Bibliographical notes.- 3 Approximation Classes.- 3.1 Approximate solutions with guaranteed performance.- 3.1.1 Absolute approximation.- 3.1.2 Relative approximation.- 3.1.3 Approximability and non-approximability of TSP.- 3.1.4 Limits to approximability: The gap technique.- 3.2 Polynomial-time approximation schemes.- 3.2.1 The class PTAS.- 3.2.2 APX versus PTAS.- 3.3 Fully polynomial-time approximation schemes.- 3.3.1 The class FPTAS.- 3.3.2 The variable partitioning technique.- 3.3.3 Negative results for the class FPTAS.- 3.3.4 Strong NP-completeness and pseudo-polynomiality.- 3.4 Exercises.- 3.5 Bibliographical notes.- 4 Input-Dependent and Asymptotic Approximation.- 4.1 Between APX and NPO.- 4.1.1 Approximating the set cover problem.- 4.1.2 Approximating the graph coloring problem.- 4.1.3 Approximating the minimum multi-cut problem.- 4.2 Between APX and PTAS.- 4.2.1 Approximating the edge coloring problem.- 4.2.2 Approximating the bin packing problem.- 4.3 Exercises.- 4.4 Bibliographical notes.- 5 Approximation through Randomization.- 5.1 Randomized algorithms for weighted vertex cover.- 5.2 Randomized algorithms for weighted satisfiability.- 5.2.1 A new randomized approximation algorithm.- 5.2.2 A 4/3-approximation randomized algorithm.- 5.3 Algorithms based on semidefinite programming.- 5.3.1 Improved algorithms for weighted 2-satisfiability.- 5.4 The method of the conditional probabilities.- 5.5 Exercises.- 5.6 Bibliographical notes.- 6 NP, PCP and Non-approximability Results.- 6.1 Formal complexity theory.- 6.1.1 Turing machines.- 6.1.2 Deterministic Turing machines.- 6.1.3 Nondeterministic Turing machines.- 6.1.4 Time and space complexity.- 6.1.5 NP-completeness and Cook-Levin theorem.- 6.2 Oracles.- 6.2.1 Oracle Turing machines.- 6.3 The PCP model.- 6.3.1 Membership proofs.- 6.3.2 Probabilistic Turing machines.- 6.3.3 Verifiers and PCP.- 6.3.4 A different view of NP.- 6.4 Using PCP to prove non-approximability results.- 6.4.1 The maximum satisfiability problem.- 6.4.2 The maximum clique problem.- 6.5 Exercises.- 6.6 Bibliographical notes.- 7 The PCP theorem.- 7.1 Transparent long proofs.- 7.1.1 Linear functions.- 7.1.2 Arithmetization.- 7.1.3 The first PCP result.- 7.2 Almost transparent short proofs.- 7.2.1 Low-degree polynomials.- 7.2.2 Arithmetization (revisited).- 7.2.3 The second PCP result.- 7.3 The final proof.- 7.3.1

Die Inhaltsangabe kann sich auf eine andere Ausgabe dieses Titels beziehen.