By Rolf Wanka
ISBN-10: 3835190679
ISBN-13: 9783835190672
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.
Read or Download Approximationsalgorithmen : eine Einführung PDF
Similar german_3 books
Dienstleistungen tragen in Deutschland erheblich zur Wertschöpfung und Schaffung von Arbeitsplätzen bei. Die Generierung von innovativen Dienstleistungen bildet somit eine wesentliche Aufgabe für die Zukunft des Wirtschaftsstandorts Deutschland. Gefragt sind Konzepte für die Professionalisierung von Dienstleistungen und die Zukunft der Dienstleistungsarbeit, die hier von renommierten Autoren aus Wissenschaft und Praxis vorgestellt werden.
- Graphenbasierte Funktionsdarstellung: Boolesche und Pseudo-Boolesche Funktionen
- Kleine Schriften zur Geschichte des Volkes Israel, Band 1
- Fw 189A Kurz-Betriebsanleitung
- Gesundheitsrisiko Heilfasten wie Heilfasten die Gesundheit schädigen kann und wie man besser dauerhaft abnimmt
- Gefährlicher Liebhaber : Jagd auf Jack the Ripper ; erotischer Gay-Roman
- Kleben - erfolgreich und fehlerfrei : Handwerk, Praktiker, Ausbildung, Industrie
Additional resources for Approximationsalgorithmen : eine Einführung
Example text
Im Fall (bl) konnen wir in der Komponente von Vj die Farben s und c/^+i vertauschen, so daB nun sowohl an u, als auch an Vj die Farbe s fehlt, wir also {w, Vj} mit s farben konnen. Im Fall (b2) konnen wir das Verschieben der Farben wie in Fall (a) mit den Kanten {w, v/^_ i } , . . , {u,Vj} durchfuhren und nun die Kante {u,Vh} entfarben. Damit ist dieser Fall auf Fall (bl) zuruckgefiihrt worden und wird nun wie dort weiterbehandelt. 10 brauchen wir eine Farbe mehr, als der Knotengrad A(G) erzwingt, da anyedem Knoten eine Farbe fehlen muB.
2 auf Seite 7 verhindert haben, daB / ( a ) = 0 sein darf, denn schlieBlich wollen wir nicht durch 0 dividieren. Ebenso haben wir dort gefordert, daB die Werte aller zulassigen Losungen gleiches Vorzeichen haben, was bei der Bewertung der Losungsqualitat durch einen Bruch ebenfalls wichtig ist. Der relative Fehler kann bei einem Minimierungsproblem beliebig groB werden, bei einem Maximierungsproblem aber nicht einmal 1. Definitionen des relativen Fehlers, die diese AsymmeU. 1 trie vermeiden, werden in den Ubungen diskutiert.
Wenden wir uns wieder dem Algorithmus zu. Der Grad eines Graphen G kann von der Anzahl ^ = |F| der Knoten abhangen, er kann sogar 0(^) sein. In diesem Fall ist die absolute Abweichung von GREEDYCOL sehr groB, er kann Ergebnisse liefem, deren Wert sehr weit vom Wert der optimalen Losung entfemt ist. 2 ab Seite 46 stellen wir einen weiteren sehr einfachen greedy Algorithmus vor, der mit 0{n/\ogn) Farben auskommt. Viel bessere Verfahren kennt man noch immer nicht, es gibt ein recht komplexes Verfahren, das asymptotisch nur „etwas" besser ist [Hal93]^.
Approximationsalgorithmen : eine Einführung by Rolf Wanka
by James
4.5