Approximationsalgorithmen: Eine Einführung

ISBN-13: 9783519004448 / Niemiecki / Miękka / 2006 / 206 str.

Rolf Wanka

Opis

Viele kombinatorische Optimierungsprobleme haben sich als schwierig exakt losbar herausgestellt, weshalb man sich mit Naherungslosungen zufrieden geben muss. In diesem Buch werden Approximationsalgorithmen vorgestellt, die fur eine Reihe popularer Optimierungsprobleme beweisbar gute Losungen in vertretbarer Zeit berechnen. Im ersten Teil werden die grundlegenden Begriffe vorgestellt, mit Beispielalgorithmen ausgefuhrt und jeweils die Grenzen aufgezeigt. Im zweiten Teil werden allgemeine Techniken eingefuhrt und anhand instruktiver Beispiele mit Leben erfullt."

Spis treści

Schnelle Algorithmen und hartnäckige Probleme - Approximation mit absoluter Güte - Approximation mit relativer Güte - Approximationsschemata - Komplexitätstheoretische Betrachtungen - Techniken für randomisierte Approximationsalgorithmen - Lineare Optimierung und Approximationsalgorithmen - Approximate Counting und die Monte-Carlo-Methode

O autorze

Prof. Dr. Rolf Wanka, Universität Erlangen-Nürnberg

Blurb

Für viele kombinatorische Optimierungsprobleme hat sich herausgestellt, daß sie vermutlich nicht durch schnelle exakte Algorithmen gelöst werden können, weshalb man sich mit Näherungslösungen zufrieden geben muß. 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.