Vor Ort
Merkzettel Warenkorb

Gutscheinbedingungen

**Gültig bis 17.08.2026 auf Schreibwaren & Office-Artikel online auf thalia.at, in der Thalia App und in teilnehmenden Thalia Buchhandlungen in Österreich mit Schulsortiment. In den Buchhandlungen nur gültig auf lagernde Ware. Einzelne Artikel können ausgeschlossen sein. Ausgenommen sind preisgebundene Artikel. Pro Einkauf einmal einlösbar. Nur gültig gegen Vorlage oder im Onlineshop hinterlegter Bonuscard. Infos zur Einlösung in der Buchhandlung sind auf der Bonuscard-Vorteilspreisseite zu finden. Click & Collect nur bei Onlinevorabzahlung möglich. Keine Einlösung bei Scan & Go-Bezahlung. Keine Barauszahlung. Nicht kombinierbar mit anderen Aktionen und Gutscheinen. Gutschein wird auf max. 500€ Bestellwert angerechnet. Nicht gültig für Geschenkkarten, Versandkosten und Services.
Produktbild: Complexity and Approximation
- 11%

Complexity and Approximation Combinatorial Optimization Problems and Their Approximability Properties

11% sparen

67,99 € UVP 76,99 €

inkl. gesetzl. MwSt., Versandkostenfrei

Beschreibung

Produktdetails

Einband

Taschenbuch

Erscheinungsdatum

03.10.2013

Verlag

Springer Berlin

Seitenzahl

524

Maße (L/B/H)

24,2/19,3/3 cm

Gewicht

1051 g

Auflage

Softcover reprint of the original 1st ed. 1999

Sprache

Englisch

ISBN

978-3-642-63581-6

Beschreibung

Produktdetails

Einband

Taschenbuch

Erscheinungsdatum

03.10.2013

Verlag

Springer Berlin

Seitenzahl

524

Maße (L/B/H)

24,2/19,3/3 cm

Gewicht

1051 g

Auflage

Softcover reprint of the original 1st ed. 1999

Sprache

Englisch

ISBN

978-3-642-63581-6

Herstelleradresse

Springer-Verlag KG
Sachsenplatz 4-6
1201 Wien
AT

Email: GPSR Kontakt

Noch keine Bewertungen vorhanden

Verfassen Sie die erste Bewertung zu diesem Artikel

Helfen Sie anderen Kundinnen und Kunden durch Ihre Meinung.

Kundinnen und Kunden meinen

Bewertungen (0)
  • Produktbild: 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.