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.
Read Online or Download Approximationsalgorithmen : eine Einführung PDF
Similar german_3 books
Dieses Buch wurde geschrieben, um die Beratungstätigkeit zu bestätigen und zu bereichern - nicht deren bankfachlichen Teil, sondern das Zusammenwirken mit den Kunden. In drei Teilen gibt es Denkanstöße zu einem ethischen, partnerschaftlichen und stilvollen Umgang mit Kunden.
Das Ende der Männer und der Aufstieg der Frauen
Ist die jahrtausendealte Herrschaft des Patriarchats am Ende? Noch nicht, sagt Hanna Rosin, doch die massiven Veränderungen der Berufswelt und des Bildungssystems haben eine Dynamik in Gang gesetzt, die das Verhältnis zwischen den Geschlechtern nachhaltig verändert. So scheinen viele Anforderungen der modernen Dienstleistungsgesellschaft – Flexibilität, soziale Intelligenz, Kommunikationsfähigkeit – eindeutig Frauen in die Hände zu spielen, während Männer oft von den Umwälzungen überfordert sind.
Grundzüge der Volkswirtschaftslehre: Eine Einführung in die Wissenschaft von Märkten
"Diesem Buch gelingt, used to be die meisten anderen nicht schaffen: begreiflich zu machen, warum es sich lohnt, dieses Fach zu studieren"(DIE WELT). So funktioniert "Volkswirtschaft zum Anfassen". Anhand von lebensnahen Beispielen wird gezeigt, wie Märkte im Großen und Kleinen funktionieren. Die Simulationen auf der begleitenden site ermöglichen es, Marktprozesse aktiv nachzuvollziehen.
Hygiene bei der Entsorgung von Siedlungsabfällen
Fragen der Hygiene spielen in der Abfallwirtschaft eine bedeutende Rolle. Schadstoffe biogener, chemischer oder physikalischer artwork dürfen weder bei der Sammlung, noch bei der Entsorgung und der Aufbereitung von Siedlungsabfällen die belebte oder unbelebte Umwelt schädigen. Mit den in der Gesetzgebung vorgegebenen Behandlungsverfahren sind Möglichkeiten zur Erreichung dieses Ziels vorhanden.
- Hydrologie und Wasserwirtschaft: Eine Einführung für Ingenieure
- Adolf Hitler, Begründer Israels
- Differentialgleichungen Lösungsmethoden und Lösungen, Band 1: Gewöhnliche Differentialgleichungen (3. Auflage)
- Arbeitsbuch zu Tiplers Physik
Additional info for Approximationsalgorithmen : eine Einführung
Example text
Information Processing Letters, 45:19-23, 1993. [HolSl] I. Holyer. The NP-completeness of edge-coloring. SIAM Journal on Computing, 10:7IS720, 1981. [Kuc91] L. Kucera. The greedy coloring is a bad probabilistic algorithm. Journal of Algorithms, 12:674-684, 1991. [RSST96] N. Robertson, D. P. Sanders, P. Seymour, and R. Thomas. Efficiently four-coloring planar graphs. In Proc. 28th ACM Symposium on Theory of Computing (STOC), pages 571-575, 1996. 1 Sei G = {V,E) ein Graph. %(G) bezeichnet die minimale Zahl an Farben, mit der man auskommt, eine Knotenfarbung von G durchzufuhren.
7 Fakt: (a) Jederplanare Graph kann in Polynomzeit mit 6 Farben knotengefarbt werden. U. 5 (b) [Der beriihmte Vier-Farben-Satz; 1977 bewiesen von Appel 8c Haken] Jederplanare Graph kann mit 4 Farben knotengefarbt werden. " ist NP-voUstandig [GJ79, S. 87ffl. (d) Es kann in Polynomzeit entschieden werden, ob ein Graph G knoten-2-farbbar ist, und, U. 4 falls ja, kann eine solche Farbung berechnet werden. Den Beweis des Vier-Farben-Satzes kann man in einen Algorithmus zur Konstruktion einer Knoten-4-Farbung verwandeln, der dann eine Laufzeit von 0(|F|2) hat [RSST96].
Dadurch wird c\ wieder zu einer an u fehlenden Farbe, und wir miissen nun {u,Vj} farben. Dazu betrachten wir den Teilgraphen H{s, c/^+i) von G, der nur aus den Kanten besteht, die mit den Farben s oder Q + I gefarbt sind, und den zugehorigen Knoten. 4: Behandlung von Fall (a). 5: Fall (b) nach dem Verschieben der Farben. M5gliche Telle von H{s^Ch+\) sind fett dargestellt. Kreise und Pfade. Die Knoten t/, Vj und Vk sind in H{s, c/^+i) sogar nur an hochstens einer Kante beteiligt, sie sind also alle Endpunkte von Pfaden des H{s,Ch-^\).