Rolf Wanka's Approximationsalgorithmen : eine Einführung PDF

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.

Show description

Read or Download Approximationsalgorithmen : eine Einführung PDF

Similar german_3 books

Download e-book for kindle: Zukunftsfeld Dienstleistungsarbeit: Professionalisierung - by Ralf Reichwald, Martin Frenz, Sibylle Hermann, Agnes

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.

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

Download PDF sample

Approximationsalgorithmen : eine Einführung by Rolf Wanka


by James
4.5

Rated 4.92 of 5 – based on 6 votes