eBook.de : Ihr Online Shop für eBooks, Reader, Downloads und Bücher

Connect 01/2015 eBook-Shops: Testsieger im epub Angebot, Testurteil: gut Die Welt: Kundenorientierte Internetseiten Prädikat GOLD
+49 (0)40 4223 6096
€ 0,00

Zur Kasse

Complexity and Approximation

Combinatorial Optimization Problems and Their Approximabili…
Lieferbar innerhalb von 2 bis 3 Werktagen
Buch (gebunden)
Buch € 90,99* inkl. MwSt.
Portofrei*
Dieses Buch ist auch verfügbar als:
Produktdetails
Titel: Complexity and Approximation
Autor/en: Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela

ISBN: 3540654313
EAN: 9783540654315
Combinatorial Optimization Problems and Their Approximability Properties.
1st ed. 1999. Corr. 2nd printing 2002.
Book w. online files/update.
Sprache: Englisch.
Springer Berlin Heidelberg

Dezember 2002 - gebunden - 548 Seiten

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.
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.

Kundenbewertungen zu Giorgio Ausiello, P… „Complexity and Approximation“

Noch keine Bewertungen vorhanden
Zur Rangliste der Rezensenten
Veröffentlichen Sie Ihre Kundenbewertung:
Kundenbewertung schreiben

Unsere Leistungen auf einen Klick

Unser Service für Sie

Zahlungsmethoden
Bequem, einfach und sicher mit eBook.de. mehr Infos akzeptierte Zahlungsarten: Überweisung, offene Rechnung,
Visa, Master Card, American Express, Paypal mehr Infos
Geprüfte Qualität
  • Schnelle Downloads
  • Datenschutz
  • Sichere Zahlung
  • SSL-Verschlüsselung
Servicehotline
+49 (0)40 4223 6096
Mo. - Fr. 8.00 - 20.00 Uhr
Sa. 10.00 - 18.00 Uhr
Chat
Ihre E-Mail-Adresse eintragen und kostenlos informiert werden:
* Alle Preise verstehen sich inkl. der gesetzlichen MwSt. Informationen über den Versand und anfallende Versandkosten finden Sie hier.
Bei als portofrei markierten Produkten bezieht sich dies nur auf den Versand innerhalb Deutschlands.

** im Vergleich zum dargestellten Vergleichspreis.
eBook.de - Meine Bücher immer dabei
eBook.de ist eine Marke der Hugendubel Digital GmbH & Co. KG
Folgen Sie uns unter: