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

Post Merger Integration von Logistikdienstleistern : konzeptionelle und empirische Analyse branchenspezifischer Integrationskompetenzen

Die Forschung zum Gebiet von Mergers & Acquisitions im Allgemeinen und der publish Merger Integration im Speziellen hat in der Betriebswirtschaftslehre eine lange culture. Obwohl im Rahmen dieser Forschungsbemühungen in der Vergangenheit bereits wesentliche Erkenntn- fortschritte erzielt werden konnten, sind die Resultate häufig relativ schwer „greifbar“.

Aufgabensammlung Elektrotechnik 2: Magnetisches Feld und Wechselstrom

BuchhandelstextEine sichere Beherrschung der Grundlagen der Elektrotechnik ist ohne Bearbeitung von ? bungsaufgaben nicht erreichbar. In diesem Band werden ? bungsaufgaben zur Wechselstromtechnik, gestaffelt nach Schwierigkeitsgrad, gestellt und im Anschluss eines jeden Kapitels ausf? hrlich mit Zwischenschritten gel?

Additional resources for Approximationsalgorithmen : eine Einführung

Sample text

2(b) handelt sich um den sog. h. den vollstandigen Graphen auf 5 Knoten, und den ^33, den vollstandigen bipartiten Graphen mit je 3 Knoten auf jeder Seite^. Beachte, daB man wirklich beweisen muB, daB die beiden Graphen nicht kreuzungsfrei U. 5 in die Ebene eingebettet werden konnen. ^Dieses Verfahren garantiert auf ^ Knoten eine absolute Giite von 0(^(loglogw) ^/(logw)^), was wirklich nur einen Hauch besser als 0{n) bzw. 0{nl\o%n) ist. ^^3^3 wird manchmal auch der Wasserwerk-Graph genannt. 2: (a) Ein planarer und (b) zwei nichtplanare Graphen.

Eine der einfachen, aber zentralen Beobachtungen in unseren Uberlegungen ist, daB man durch das Entfemen einer Kante aus einer Rundreise einen Spannbaum erhalt. 2)). Diese Beobachtung wird auch im bekannten exakten Branch&BoundAlgorithmus fur TSP eingesetzt. Hier werden systematisch rekursiv alle moglichen Rundreisen ausprobiert. Hat man schon eine Tour berechnet und versucht eine weitere Tour zu konstruieren, von der man schon einen Teil festgelegt hat, so kann man den Beitrag der noch fehlenden Knoten durch das Gewicht eines minimalen Spannbaum nach unten abschatzen.

Er hat eine Giitegarantie von 0{n/\ogn) und verfolgt ebenfalls einen greedy Ansatz: Auf einen Schlag werden so viele Knoten gleichzeitig mit der gleichen Farbe gefarbt, wie man erlaubt finden kann. Insofem ist der neue eine natiirliche Erweiterung des ersten Algorithmus. Knotenmengen, die man mit der gleichen Farbe farben kann, nennt man „unabhangig" und auch „stabil". Die Bestimmung groBer derartiger Mengen behandelt der folgende Abschnitt. 10 Definition: Sei G = (V^E) ein Graph, und SQI U CV eine Knotenmenge.

Download PDF sample

Rated 4.59 of 5 – based on 44 votes