Approximationsalgorithmen : eine Einführung by Rolf Wanka

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

Similar german_3 books

Sozialpolitik und soziale Lage in Deutschland. Band 2: Gesundheit, Familie, Alter und Soziale Dienste. 5. Auflage

Das überarbeitete Hand- und Lehrbuch bietet in zwei Bänden einen breiten empirischen Überblick über die Arbeits- und Lebensverhältnisse in Deutschland und die zentralen sozialen Problemlagen. Im Mittelpunkt der Darstellung stehen Arbeitsmarkt, Arbeitslosigkeit und Arbeitsbedingungen, Einkommensverteilung und Armut, Krankheit und Pflegebedürftigkeit sowie die Lebenslagen von Familien und von älteren Menschen.

Erläuterungen zu Christa Wolf, Kassandra

In Kassandra greift Christa Wolf auf einen Mythos des abendländischen Patriarchats zurück, den Trojanischen Krieg. Während Kassandra, die Seherin, auf dem Beutewagen des Agamemnon sitzt, überdenkt sie noch einmal ihr Leben. Mit ihrem Ringen um Autonomie legt sie Zeugnis ab von weiblicher Erfahrung in der Geschichte

Extra resources for Approximationsalgorithmen : eine Einführung

Example text

2: Beispiel fur Christofides' Algorithmus: (a) Ein MST; (b) ein leichtestes Matching und die Euler-Tour; (c) Loschen von Duplikaten. 8 Satz: ([Chr76]) C H , gestartet mit einer Eingabe aufn Knoten, garantiert eine relative Giite von pen < i ~ ^• Seine Laufzeit ist 0{n^-^ (log^)^). h. c{R*) = OPT(/). *) ist. *, die mindestens die Lange c{R*)/n hat, fiir die also c{e) > c{R'')/n gilt. Entfemt man e aus dem Hamiltonkreis R*, erhalt man einen Spannbaum des K^. *) / . 2) n \ n/ Zu (2): DaB in einem (beliebigen) Baum die Anzahl der Knoten mit ungeradem Grad gerade ist, kann man ganz einfach induktiv nach der Struktur des Baumes zeigen.

D Da es Graphen gibt, die mindestens A(G) + 1 Farben zur Kantenfarbung bendtigen (z. B. die vollstandigen Graphen mit ungerader Anzahl an Knoten), kann die Aussage des Satzes von U. 6 Vizing nicht scharfer formuliert werden. 11 Satz: Algorithmus luteGiitel. FARBEKANTEN kann in Zeit0{\V\'\E\) ausgefahrt werden undgarantiertabso- U. 8 U. 9 DaB die absolute Abweichung ebenfalls 1 ist, wird in den Ubungen behandelt. Wie bereits erwahnt, ist das Entscheidungsproblem, ob ein Graph G mit A(G) Farben kantengefarbt werden kann, NP-vollstandig [H0I8I].

Nun gilt OPT(/') — fp{oA') < k wegen Schritt 2. Da es fiir I' keine zulassigen Losungen mit dieser Eigenschaft auBer den optimalen Losungen gibt, ist CA' eine optimale Losung fiir P und damit auch fiir /. D Dieser Beweis enthalt eine typische Vorgehensweise, um zu zeigen, daB ein Problem schlecht approximierbar ist: Durch eine Transformation der urspriinglichen Probleminstanz / von n in eine Probleminstanz I' von n ' wird die Liicke zwischen dem optimalen Wert und dem nachstbesten nichtoptimalen Wert, die fiir / relativ klein ist, in P sehr groB.

Download PDF sample

Rated 4.85 of 5 – based on 12 votes