Complexity and Approximation

Combinatorial Optimization Problems and Their Approximability Properties

Inbunden, Engelska, 1999

AvGiorgio Ausiello,Pierluigi Crescenzi,Giorgio Gambosi,Viggo Kann,Alberto Marchetti-Spaccamela,Marco Protasi,Giorgio Ausiello,Pierluigi Crescenzi

1 169 kr

Beställningsvara. Skickas inom 10-15 vardagar. Fri frakt för medlemmar vid köp för minst 249 kr.

Finns i fler format (1)

Häftad

959 kr

Skickas inom 10-15 vardagar

This book is an up-to-date documentation of the state of the art in combinatorial optimization, presenting approximate solutions of virtually all relevant classes of NP-hard optimization problems. The well-structured wealth of problems, algorithms, results, and techniques introduced systematically will make the book an indispensible source of reference for professionals. The smooth integration of numerous illustrations, examples, and exercises make this monograph an ideal textbook.

Produktinformation

Utgivningsdatum1999-11-09
Mått203 x 254 x 34 mm
Vikt1 256 g
FormatInbunden
SpråkEngelska
Antal sidor524
Upplaga1999
FörlagSpringer-Verlag Berlin and Heidelberg GmbH & Co. KG
ISBN9783540654315

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.