Download Approximationsalgorithmen : eine Einführung by Rolf Wanka PDF

By Rolf Wanka

Viele kombinatorische Optimierungsprobleme haben sich als schwierig exakt lösbar herausgestellt, weshalb guy sich mit Näherungslösungen zufrieden geben muss. In diesem Buch werden Approximationsalgorithmen vorgestellt, die für eine Reihe populärer Optimierungsprobleme beweisbar gute Lösungen in vertretbarer Zeit berechnen. Im ersten Teil werden die grundlegenden Begriffe vorgestellt, mit Beispielalgorithmen ausgeführt und jeweils die Grenzen aufgezeigt. Im zweiten Teil werden allgemeine Techniken eingeführt und anhand instruktiver Beispiele mit Leben erfüllt.

Show description

Read Online or Download Approximationsalgorithmen : eine Einführung PDF

Best german_3 books

Karriereberatung. Coachingmethoden für eine kompetenzorientierte Laufbahnberatung, 2. Auflage

Der Wandel von der stabilen Erwerbsbiografie zur instabilen Patchworklaufbahn verlangt von Karriere- und Berufsberatern eine besondere Herangehensweise. Die Autoren stellen Coaching-Methoden vor, die Personen in beruflichen Umbruchsituationen bei der aktiven Gestaltung des Berufswegs helfen und vorhandene Ressourcen aktivieren.

Grundkurs Theoretische Physik: 4 Spezielle Relativitätstheorie Thermodynamik

InhaltSpezielle Relativit? tstheorie: Grundlagen - Kovariante vierdimensionale Formulierung - Thermodynamik: Grundbegriffe - Haupts? tze - Thermodynamische Potentiale - Phasen und Phasen? berg? ngeZielgruppeStudenten der Physik im Grundstudium? ber den Autor/HrsgProf. Dr. Wolfgang Nolting arbeitet auf dem Gebiet der Festk?

Extra resources for Approximationsalgorithmen : eine Einführung

Sample text

Sei M diejenige der beiden, fiir die c{M) < \c{R) < \c{R*) gilt, und sei Z die Menge der Knoten, die je Kante von M den kleineren cost-Wert haben, d. h. Wij^^} G M}. Die Wahl von Z hangt von der Heuristik ab, d. h. 1 Das metrische Traveling Salesperson Problem 41 Abfolge stattfindet! 5 angewandt wurde. ^+i = R£ — Z£ fiir ^ > 1. 6 fiir jedes Ri gilt. ,v4) = cost(IJZ^) = Xcost(Z^) < ([log^] + 1). OPT(/) sind. 4) Bis heute ist nicht bekannt, ob diese obere Schranke fiir die relative Giite dieser Heuristik scharf ist.

Womit die Behauptung folgt. n ^Dies ist das Standardbeispiel einer Anwendung der Cauchy-Schwarzschen Ungleichung: Fiir welches x -(xi,... ,Xk) mit ^Xi = n wird s{x) = ^xj minimal? Antwort: Xi = n/k und damit s(x) = n^/k. 5: Gbad mit n Knoten: ein \{n — 1)-Zeuge gegen GREEDYIS. Analyse von GREEDYIS in Abhangigkeit von der chromatischen Zahl Da isolierte Knoten, d. h. Knoten ohne Kanten, sowohl fiir das Farbungsproblem wie fiir IS irrelevant sind, gehen wir in den folgenden Analysen davon aus, daB der Eingabegraph immer mindestens eine Kante besitzt und damit mindestens 2 Farben fur die Knotenfarbung benotigt.

GJ79] M. R. Garey and D. S. Johnson. Computers and Intractability - A Guide to the Theory of NP-Completeness. Freeman, New York, 1979. [Hal93] M. M. Halldorsson. A still better performance guarantee for approximate graph coloring. Information Processing Letters, 45:19-23, 1993. [HolSl] I. Holyer. The NP-completeness of edge-coloring. SIAM Journal on Computing, 10:7IS720, 1981. [Kuc91] L. Kucera. The greedy coloring is a bad probabilistic algorithm. Journal of Algorithms, 12:674-684, 1991. [RSST96] N.

Download PDF sample

Rated 4.99 of 5 – based on 16 votes