Complexity and Approximation Combinatorial Optimization Problems and Their Approximability Properties
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 computat...
| Main Authors: | , , , |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
Berlin, Heidelberg
Springer Berlin Heidelberg
1999, 1999
|
| Edition: | 1st ed. 1999 |
| Subjects: | |
| Online Access: | |
| Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
Table of Contents:
- 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
- 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
- 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