Combinatorial Optimization Problems and Their Approximability Properties
Buch, Englisch, 524 Seiten, Format (B × H): 193 mm x 242 mm, Gewicht: 1051 g
ISBN: 978-3-642-63581-6
Verlag: Springer
This book documents the state of the art in combinatorial optimization, presenting approximate solutions of virtually all relevant classes of NP-hard optimization problems. The wealth of problems, algorithms, results, and techniques make it an indispensible source of reference for professionals. The text smoothly integrates numerous illustrations, examples, and exercises.
Zielgruppe
Professional/practitioner
Autoren/Hrsg.
Fachgebiete
- Wirtschaftswissenschaften Betriebswirtschaft Management Entscheidungsfindung
- Wirtschaftswissenschaften Betriebswirtschaft Unternehmensforschung
- Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen Numerische Mathematik
- Mathematik | Informatik Mathematik Mathematik Allgemein Diskrete Mathematik, Kombinatorik
- Mathematik | Informatik EDV | Informatik Informatik Mathematik für Informatiker
- Wirtschaftswissenschaften Betriebswirtschaft Wirtschaftsmathematik und -statistik
- Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Software Engineering
- Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Algorithmen & Datenstrukturen
- Mathematik | Informatik EDV | Informatik Professionelle Anwendung
Weitere Infos & 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.
