Comprehensive Assessment of numerous problems in combinatorial optimization

Includes supplementary material: [...]

1 The Complexity of Optimization Problems.- 1.1 Analysis of algorithms and complexity of problems.- 1.2 Complexity classes of decision problems.- 1.3 Reducibility among problems.- 1.4 Complexity of optimization problems.- 1.5 Exercises.- 1.6 Bibliographical notes.- 2 Design Techniques for Approximation Algorithms.- 2.1 The greedy method.- 2.2 Sequential algorithms for partitioning problems.- 2.3 Local search.- 2.4 Linear programming based algorithms.- 2.5 Dynamic programming.- 2.6 Randomized algorithms.- 2.7 Approaches to the approximate solution of problems.- 2.8 Exercises.- 2.9 Bibliographical notes.- 3 Approximation Classes.- 3.1 Approximate solutions with guaranteed performance.- 3.2 Polynomial-time approximation schemes.- 3.3 Fully polynomial-time approximation schemes.- 3.4 Exercises.- 3.5 Bibliographical notes.- 4 Input-Dependent and Asymptotic Approximation.- 4.1 Between APX and NPO.- 4.2 Between APX and PTAS.- 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.3 Algorithms based on semidefinite programming.- 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.2 Oracles.- 6.3 The PCP model.- 6.4 Using PCP to prove non-approximability results.- 6.5 Exercises.- 6.6 Bibliographical notes.- 7 The PCP theorem.- 7.1 Transparent long proofs.- 7.2 Almost transparent short proofs.- 7.3 The final proof.- 7.4 Exercises.- 7.5 Bibliographical notes.- 8 Approximation Preserving Reductions.- 8.1 The World of NPO Problems.- 8.2 AP-reducibility.- 8.3 NPO-completeness.- 8.4 APX-completeness.- 8.5 Exercises.- 8.6 Bibliographical notes.- 9 Probabilistic analysis of approximation algorithms.- 9.1 Introduction.- 9.2 Techniques for the probabilistic analysis of algorithms.- 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.4 Heuristics based on local 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.