Complexity and Approximation als Buch
PORTO-
FREI

Complexity and Approximation

Combinatorial Optimization Problems and Their Approximability Properties. 1st ed. 1999. Corr. 2nd printing 2002.…
Buch (gebunden)
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, r … weiterlesen
Dieses Buch ist auch verfügbar als:
Buch

90,99 *

inkl. MwSt.
Portofrei
Lieferbar innerhalb von zwei bis drei Werktagen
Complexity and Approximation als Buch

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

3. Dezember 2002 - gebunden - 548 Seiten

Beschreibung

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 computations with arbitrary precision and we have to truncate the representation of real numbers. In other cases, we use to approximate com plex mathematical objects by simpler ones: for example, we sometimes represent non-linear functions by means of piecewise linear ones. The need to solve difficult optimization problems is another reason that forces us to deal with approximation. In particular, when a problem is computationally hard (i. e. , the only way we know to solve it is by making use of an algorithm that runs in exponential time), it may be practically unfeasible to try to compute the exact solution, because it might require months or years of machine time, even with the help of powerful parallel computers. In such cases, we may decide to restrict ourselves to compute a solution that, though not being an optimal one, nevertheless is close to the optimum and may be determined in polynomial time. We call this type of solution an approximate solution and the corresponding algorithm a polynomial-time approximation algorithm. Most combinatorial optimization problems of great practical relevance are, indeed, computationally intractable in the above sense. In formal terms, they are classified as Np-hard optimization problems.

Inhaltsverzeichnis

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.
Servicehotline
089 - 70 80 99 47

Mo. - Fr. 8.00 - 20.00 Uhr
Sa. 10.00 - 20.00 Uhr
Filialhotline
089 - 30 75 75 75

Mo. - Sa. 9.00 - 20.00 Uhr
Bleiben Sie in Kontakt:
Sicher & bequem bezahlen:
akzeptierte Zahlungsarten: Überweisung, offene Rechnung,
Visa, Master Card, American Express, Paypal
Zustellung durch:
¹ Mängelexemplare sind Bücher mit leichten Beschädigungen, die das Lesen aber nicht einschränken. Mängelexemplare sind durch einen Stempel als solche ge-
kennzeichnet. Die frühere Buchpreisbindung ist aufgehoben.
* Alle Preise verstehen sich inkl. der gesetzlichen MwSt. Informationen über den Versand und anfallende Versandkosten finden Sie hier.
** Deutschsprachige eBooks und Bücher dürfen aufgrund der in Deutschland geltenden Buchpreisbindung und/oder Vorgaben von Verlagen nicht rabattiert werden. Soweit von uns deutschsprachige eBooks und Bücher günstiger angezeigt werden, wurde bei diesen kürzlich von den Verlagen der Preis gesenkt oder die Buchpreisbindung wurde für diese Titel inzwischen aufgehoben. Angaben zu Preisnachlässen beziehen sich auf den dargestellten Vergleichspreis.