Complexity and Approximation

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 Normal form verifiers.- 7.3.2 The composition lemma.- 7.4 Exercises.- 7.5 Bibliographical notes.- 8 Approximation Preserving Reductions.- 8.1 The World of NPO Problems.- 8.2 AP-reducibility.- 8.2.1 Complete problems.- 8.3 NPO-completeness.- 8.3.1 Other NPO-complete problems.- 8.3.2 Completeness in exp-APX.- 8.4 APX-completeness.- 8.4.1 Other APX-complete problems.- 8.5 Exercises.- 8.6 Bibliographical notes.- 9 Probabilistic analysis of approximation algorithms.- 9.1 Introduction.- 9.1.1 Goals of probabilistic analysis.- 9.2 Techniques for the probabilistic analysis of algorithms.- 9.2.1 Conditioning in the analysis of algorithms.- 9.2.2 The first and the second moment methods.- 9.2.3 Convergence of random variables.- 9.3 Probabilistic analysis and multiprocessor scheduling.- 9.4 Probabilistic analysis and bin packing.- 9.5 Probabilistic analysis and maximum clique.- 9.6 Probabilistic analysis and graph coloring.- 9.7 Probabilistic analysis and Euclidean TSP.- 9.8 Exercises.- 9.9 Bibliographical notes.- 10 Heuristic methods.- 10.1 Types of heuristics.- 10.2 Construction heuristics.- 10.3 Local search heuristics.- 10.3.1 Fixed-depth local search heuristics.- 10.3.2 Variable-depth local search heuristics.- 10.4 Heuristics based on local search.- 10.4.1 Simulated annealing.- 10.4.2 Genetic algorithms.- 10.4.3 Tabu search.- 10.5 Exercises.- 10.6 Bibliographical notes.- A Mathematical preliminaries.- A.1 Sets.- A.1.1 Sequences, tuples and matrices.- A.2 Functions and relations.- A.3 Graphs.- A.4 Strings and languages.- A.5 Boolean logic.- A.6 Probability.- A.6.1 Random variables.- A.7 Linear programming.- A.8 Two famous formulas.- B A List of NP Optimization Problems.