Merken

Primal-Dual-Approximationsalgorithmen II

Zitierlink des Filmsegments
Embed Code

Automatisierte Medienanalyse

Beta
Erkannte Entitäten
Sprachtranskript
oder eine n
herzlich willkommen zur Vorlesung diskreter Optimierung wir werden heute wieder weiter über Trimmal duale Approximation zu Algorithmen reden ziel ist das finde sehr breite Terrasse von allen Problemen die vor allem wenn es darum geht Netzwerke zu designen auftreten für solche Probleme einen guten Approximation zu Algorithmus zu beweisen und dazu werden jetzt eben dieses Primal duale Verfahren haben das heißt das Ziel wird sein für genau erst mal sich diese Klasse von Problemen noch mal anzusehen und dann zu versuchen mit dem Verfahren das wir auch schon das letzte Mal gesprochen haben eine ein guten schnellen Approximation es Algorithmus zuweist also ist das 1. Ziel sich nochmal das Problem das hat mir auch schon das letzte Mal nochmal anzuschauen das Problem was wir betrachten ist das Fittings hat Probleme das heißt gegeben gegeben ist uns eine Grundmenge die wir ihnen
außerdem sind uns gegeben Teilmengen dieselben Grundmenge E wir sind uns Teilmengen dieser dieser Grundmenge und eine und Gewichte CE größer gleich neue für aus E sei sie aber auf den Elementen noch gewichten und gesucht es ist eine Teilmenge A A aus E die Gewichts minimal ist die Gewichts minimales unter der Bedingung das für alle die aus 1 bis B gilt das CEE geschnitten mit dieser Menge A nicht die leere Menge ist daher auch der Name hitting seit wir wollen alle die man T treffen das erst mal so ganz abstrakt das Problem die Frage wofür ist das gut und da werd ich ein bisschen vorgreifen zu dem was im Skript steht und man ein Problem herauspicken wo das auftritt wenn ich das so genannte Steiner Baum Problem und dies Steiner Baum Problem es relativ viel betrachtet worden aus dem einfachen Grund weil es eben gerade zum Beispiel bei beim Chip-Design und ähnlichen auf gaben immer wieder auftritt die Idee es ich habe einen Gras und um die Analogie zum Chip-Design bisschen deutlich zu machen nämlich ein Gitter Grafen ich hab ein Dieter Grafen oder irgendein Grafen erstmal gegeben und meine Grundmenge sind in dem Fall die Kanten und zusätzlich habe ich geben eine Menge die klassischerweise T genannt wird und das sind die sogenannten schwärmen aus und die Idee von diesem und das sind meistens eben elektronische Komponenten oder ähnliches auf diesem Chip die sind ja irgendwie verteilt und zwar so die müssen alle über eine Verkabelung verbunden werden also dass dieses ich muss irgendwie eine Möglichkeit finden diese 3 miteinander zu verbinden das heißt wenn ich nur 2 hätte wär es einfachen kürzeste Wege Problem ich hab aber 3 das heißt ich muss an irgendeiner Stelle mich mal entscheiden muss mich an irgendeiner Stelle mal entscheiden so was zu machen ich muss sozusagen hier irgendwie so ne Art Baumstruktur darein denn das hat ihm auch das Steiner Baum Probleme natürlich wenn man Chip-Design machten will muss man viele Steine aber Probleme lösen und die Dinger dürfen sich auch nicht überschneiden aber Steiner wolle man Dieter Grafen schnell zu finden ist eben eine Teilaufgabe die da immer auftritt und die wir hier als Fittings hat Problem formulieren können wenn das sehr einfach sagen es wir haben sie eben unserem Grafen G der eben aus Knoten V und Kanten besteht und es sind eben genau die Kanten auf unsere Meetings hat Problem und die TI sind einfach irgendwelche Teilmengen aus V und zwar so das die geschnittene C nicht leer ist also ich nehme mir irgendwelche kannten Knoten dar und wenn mir irgendwelche Knoten schnell mir irgendwelche Knoten und teile die so auf dass irgendwelche dieser das in dieser Knoten Menge drin liegen aber eben auch das die geschnitten mit TV On The also die Knoten die nicht haben wird sind auch leer ist auch nicht leer ist das heißt das Ziel das ich suche mir Knoten Mengen digitalen als in 2 Teile teilen also unbeschadet haben in dem einen und dem fÃrdert haben als in dem anderen sind und dann ist klar dass wenn nicht sage ich würde gerne hätte gerne das sozusagen der Schnitt also die kann jetzt über diese dies geben die eben diese 2 Komponenten verbinden da muss halt eine rüber gehen denn sonst hab ich keine Ware Schreiner Baum hier er hat jetzt hier mir die Notation eine Ungenauigkeit erlaubt sie zu identifizieren eigentlich mit eben was ich hier als Delta T i hätte das ist halt etwas unsauber also dem schnellt der induziert wird von dieser Knoten Menge das ist und Standard Graphentheorie Mehr also ich mache es gerne sagen wir so es ist eine Garten theoretische Ungenauigkeit eben den Schnitt der von der Knoten Menge induziert wird mit dieser Knoten Menge zu identifizieren nochmal zur Wiederholung Einschnitt in einem Grafen entsteht eben einfach wenn ich ein paar Knoten nehme und mir genau eben die dazu zugehörige Menge Abnehmer und dann einfach die Klanten angucke die hier irgendwie drüber gehen die diese 2 Komponenten verbinden und im Wesentlichen sind das sozusagen in der 2 Probleme die wir immer betrachten werden das ist einmal das Schwein aber ein Problem das andere hatten wir das letzte Mal dass war dich sozusagen in verschiedenen Varianten dargestellt das war das kürzeste lege Problem da bestanden die Schnitte dich betrachtet habe genau einfach aus 2 Teilmengen oder Zielknoten in dem ein und der Startknoten einer anderen Komponente war da nicht genau diese Schnitte als The is für meine Meetings hat Problem genommen wenn ich einen minimal auf spannenden Baum haben wir etwas was wir auch schon in der Vorlesung gesehen hab ich mir einfach alle Teilmengen der Knoten Menge und sage ich hätte gerne dass jede Teilmenge eben überbrückt wird genauso werden wir dann gibt es ne gerichtete Variante von diesem Problem das minimal aber was denn das Problem auch da will ich einfach wieder das über jede Kante sozusagen geriet die richtige die richtig gerichtete Kante drüber geht Varianten davon wenn man hier in dem er ich wenn man hier sozusagen nicht fordert dass sie einmal trifft sondern dass sie sozusagen gewisse Mindestzahl treffen also das heißt dass ich eben nicht einmal dass ich hier nicht einfach nur habe ist die leere Menge sondern ist enthält mindestens 2 Element oder mindestens 3 Elemente kriege ich ein Problem das man
als so weit über Network Design nennt das heißt wo es darum geht ein Netzwerk zu designen sodass eben so das eben eine ein gewisser mindest Zusammenhang von diesem Netzwerk gesichert ist das meist durch eine Verbindung kappen kann und das Netzwerk bleibt zusammenhängt das sind die Probleme die ebenso zeigen sich alle in dieses Setting Site Muster eintragen lassen und daher ganz für uns halt interessant sein eine Approximation sei Algorithmus für dieses allgemeine Problem zu beweisen für den Approximation so wird man für diese speziellen Probleme die tatsächlich auch relevant sind auftreten werden und genau deshalb haben die Leute das gemacht deshalb haben sich diese Verallgemeinerung angekuckt Wahlleiter angefangen haben Approximation sein 3. für das Steiner Baum Problem zu finden Approximation es Algorithmen für andere spezielle Probleme gesagt dann gut da muss doch irgendwie ein allgemeines Muster dahinter stecken Orient daher ist das sozusagen der Rahmen in dem wir uns bewegen und wo wir uns jetzt herantasten müssen und da müssen wir dann die spezielle Problem Struktur die sozusagen bisschen spezieller ist als einfach nur Meetings hat ausnutzen wenn wir dann tatsächlich was über die Approximation Scythe beweisen wollen das heißt dann wissen wir tatsächlich Anfang bisschen auszunutzen welches Problem von den vielen die wir haben jetzt wirklich haben das wird dann manchmal zu etwas technischen Bedingungen aber das ist sozusagen die die die Idee dahinter nochmal zur Wiederholung jetzt nachdem ich so sein glaube vom bisschen umrissen habe was sozusagen der Hintergrund dieser komischen Formulierung ist noch mal die IP Formulierung davon die PIN Formulierung ist relativ klar ich mache einfach ich minimiere C transponiert x wobei x einfach jetzt 1 Euro 0 1 Variable ist die uns eben sagt ob die kannte und es ist also ob sozusagen hier das Element aus der Grundmenge X ausgewählt worden ist oder nicht sehr Grundmenge E und das wird eben gerne hätten ist das die so Mehr aller ihr aus E er ist die Summe aller vermisst direkt so alle Summer Ort die in TI drinliegen XE das muss größer gleich 1 zu 1 das ist genau diese wir müssen treffen Bedingung ja ich hab hier diese Teilmengen und ich möchte eben genau das dieses dass in diesem X 1 kodiert ist dass das eben genau und hier sagt das muss getroffen werden wenn uns jetzt die LP Formulierung dazu angucken wie sieht die aus naja wenn ich das hier Galaxien ihre ist klar dass durch das Menü am erzwungen wird das das Exil 4 nicht größer als 1 wird er ist ein auf 1 gesetzt dann hab ich die Bedingungen für den gibt überhaupt keinen Grund warum das X größer sein sollte das heißt ich kann das Relax zieren so minimiere C transponiert X wenig DLP Relax ierung werde die zum I X die größer gleich 1 und X ist einfach nur größer gleich 0 und das ist unser prima alles LP das duale Problem dazu bis eben maximiere die Summe Mehr wie von 1 bis P eben genau für jedes T kriegen wir eine globale Variable Maximierung in die Summe werde y und ankündigt für jede für alle ihr aus E wie kriege ich eben auch für alle die das für alle die aus E bekomme ich jetzt die Bedingung dass die Summe über die so dass die TI enthalten ist das ist einfach jetzt genau symbolisch transponiert was ich hier mache y i das für uns kleiner gleich weil die X ja nun mal alle nicht negativ an das soll 2 1 gleich sie Seite und y s größer gleich 0 weil das ja auch eben eine größer gleich die ab das ist unser duales Problem das heißt die Idee dass ich gehe hin und hab ihr die Bedingung dass meine geboren Variable y e zusammen höchstens CEN geben was und aus dem Schlupf und das war die Diskussion von letztem aus der Diskussion um den komplementären Schlupf weiß ich eben dass hier Gleichheit herrscht dass das nehmen oder dass mir das nur erlaubt hier dieses Sixto erhöht und das sehr grobe Vorgehen beim Primal Dual Algorithmus wird sein diese y ist der Reihe nach zu erhöhen denn wir wissen dass wir von y gleich 0 starten können weil das eine zulässige Lösung aus die der Reihe nach zu erhöhen und zwar so lange bis wir irgendwo ich auf der Gleichheit stoßen und das Element so sagen die Nebenbedingung Wurche Gleichheit Auftritt tatsächlich dann oben auf 1 zu setzen weil das der einzige sinnvolle wert ist den wir hier oben haben und das interessante wird sein wir werden immer versuchen hier irgendwas zu konstruieren was ganzzahlig ist dann werden wir halt hier nicht mehr die zu sagen wenn wir echte Dualität Lücke zwischen diesen beiden Problemen bekommen weil wir hier nicht unbedingt ganzzahlig sein müssten aber dies ist hier und da dieser Ausdruck hier die Zielfunktion des dualen wird uns erlauben untere Schranke für den Funktionswert dieses LPs anzugehen und das erlaubt uns dann tatsächlich Approximation Skythen zu beweisen das ist sozusagen dieses Ding hier umzuschreiben zu überlegen wie wir damit umgehen das wird uns helfen Approximation Skythen zu beweisen was ich jetzt schon mal eingehen möchte wenn das Problem wenn die kann wenn das zum Grafen Problem es von dieser Form Steiner Baum oder ähnliches und die Kantenlängen euklidischer Abstände sind also in Ebene sind und die Kantenlängen genau euklidischer Abstände sind dann gibt es tatsächlich eine sehr schöne Variante sich zu visualisieren was dieser Algorithmus tut und zufällig haben wir sowas auch in bei uns in der Arbeitsgruppe hängt deshalb zeige ich das mal wer wir uns die Dual Variablen visualisieren können und wir werden es später dann nochmal detaillierter untersuchen ist das wir sehen das ihr sozusagen kleine Kreise immer größer werden und das ist das Vergrößern der Dual Variablen solange bis sie aneinander stoßen das entspricht dem das wir hier Gleichheit kriegen und dann muss bekannter eingefügt werden das ist genau sagen Ideen die wir hier mal machen wir lassen sozusagen diese globale Variablen wachsen das sind hier diese kreisen weiß ihr Mann von hinten irgendwie sieht das die unterschiedlich gefärbt sind also sozusagen immer von Geld ist sozusagen vom dunkleres Orange und das entspricht den unterschiedlichen runden die dieser Algorithmus gemacht hat in der 1. Runde kam so dieser hellgelben dazu dann kam die etwas dunkleren und so weiter und so fort und irgendwann erhalten leben sollen euklidischen minimal auf spannende Baum ist eben 1 2 Approximation dazu und das ist sozusagen das Ziel zu überlegen war wird wie dieses Bild jetzt hier zustande kommt und wie man dazu zu diesem zu diesem Ergebnis hier kommt ein das auf jeden Fall schon eine ganz gute Visualisierung sich zu überlegen wie man die man sich diesen Lauf des Algorithmus vorstellen muss immer wenn so 2 Kreise miteinander zusammenstoßen muss sich eine neue kannte einführen das ändern uns noch an die Grundversion das hatten wir auch dass das hat mir das letzte mal schauen wo ich gerade noch mal dass ich hier nicht die Zahlen durcheinander bringen die Grundversion
die 1. Verbesserung mit sich bringen direkt Algorithmus 6 15 aus dem Skript nochmal der ging so das wir anfingen und sagt ja y soll 0 sein unsere Ausgangsmenge aber soll die leere Menge sein ich mach das jetzt mal explizit um wirklich das Skript auch genau zu übernehmen mit Stella das hat wir das letzte Mal nicht also wir setzen das ist einfach nur mit hätten Zähler auf 0 erzählt uns wie viele Elemente wie in dem Art und haben und dann sagen wir einfach so lange es ein K gibt so das geschnitten mit die leere Menge ist also sozusagen solang K das verletzende Element ist wir also hier oben in den prima ein Programm Nichtzulässigkeit haben erhöhen wir y k also die zugehörige Dual Variable bist es eine Kante ihn gibt so dass eben genauer die Bedingung aus dem dualen ich hiermit Gleichheit erfüllt wird das muss ein X E an Quatsch müssen y stehen es an E gleichziehen und das nennen wir dann E l einfach das i-was Elton Schritt zurück geführt gefunden wurde das ist jetzt schon aber haben wir wie der L wird auf L +plus 1 gesetzt ich mobil das immer so ein das es Schritt 5 und das ist Schritt 6 und dann setzen wir eben in Schritt 7 A =ist gleich vereinigt mit diesen ideellen also wir fügen E l jetzt dem Arzt zu Na ja den n Schritt lass ich mal und dann kommt sozusagen interessante teilen wir haben gesehen häufig zumindest in der Diskussion dass wie wenn wir diesen Algorithmus so durchführen dass das aber was am Ende rauskommt tendenziell zu groß wird zu viele Elemente enthalten wird weil eben zum Beispiel wenn wir das für den minimal aufspannen Baum machen wir eben einen in wird er für den Verbrauch für den kürzesten Weg dies Problem anwenden tatsächlich meistens sowas wie ein aufspannen den kürzesten Wege Baum bekommen deshalb ab ich wollte mir noch kannten laschen das heißt wir zählen jetzt durch durch alle kannten und fangen dabei bei der letzten Kanther an und zwar wenn wie die Kante E J entfernen können ohne dass wenn Problem mit der Zulässigkeit kriegen ob Eichel daran setzen da und dann löschen sie halt einfach meine wenn kein Problem mit der zu setzen so Zulässigkeit kriegen da die Kosten nicht negativ sind tun wir uns damit nix wenn wir das Ding einfach rauswerfen also setzen wir gleich aber ohne er hat und
das ist dann auch schon sozusagen das Ende des Algorithmus sich das er sozusagen die letzte Version des Algorithmus die wir hatten die Idee war wir gehen hin fügen der Reihe nach alle mentalen ein immer wenn wir hier sozusagen an die Grenze stoßen also identifizieren unzulässige Bedingung erhöhen die entsprechende Dual variable solange bis wir an die Grenzen stoßen für irgendeine kannte jetzt in unserem Fall zum Beispiel und in dem Moment wo das passiert ich diese Kanther ein und wenn ich damit fertig bin natürlich wieder rückwärts so lange kannten raus bis ich da unten es sich irgendwie mal beziehungsweise überschlich kam raus immer wenn es für die Zulässigkeit kein Problem darstellt das uns eine verbesserte Variante eben mit rückwärts Löschung wie man sagt und das Ziel ist jetzt natürlich dafür war Approximation Skythen zu beweisen und da hatten wir schon 2 die eine Approximation Scythe die wir hatten galt sogar für die Grundversion für die Grundversion von diesem Algorithmus und zwar lag das daran dass sehr klar ist was ist das Problem also warum wird dieser Algorithmus vielleicht mein Problem kriegen der könnte ein Problem kriegen gab ich dass sich jedes dieser Sites was sich treffen muss 11. Treffer als ich eigentlich muss denn es ist ja klar wenn wir jetzt sagen wir wissen wir haben LTE wir wissen sozusagen einfach aus LP Moralität dass die Sommer zentral an war es auch sehr transponiert X das muss größer sein für jetzt sagen wir 1 x schwer anders gehen würdest das muss ja größer sein als Na ja das muss größer sein als die Summe über Willi gleich 1 bis P der y Stern die also wenn X Stern würdest P und y Stern löst die als Taipeh Dualität und das geht natürlich auch wenn dieses extern irgendwie die ganzzahlige Lösung ist die hier aus diesem Algorithmus rausfällt das heißt es klar dass gilt ist das hier und wenn es gerade noch einmal das Kind erst mal aber ich kann mich ja sogar noch einschränken denn ich kenne ja hier sozusagen diese Konstruktion die Mehr sagt dass dieses C E für jetzt gegebene Lösung hier das diesen Sommer ja ich will es der Sommer der E aus E C E wobei aber dass da wir wissen dass wir eigentlich zulässig sind können wir setzen das Ganze durch ihr aus aber das heißt wir wissen wir müssen ja nur die aufsummieren dieser Menge A drin lag und das ist aber gleich da wir wissen dass wir genau die und das ist die Konstruktion hier oben das wir die hiermit Gleichheit erfüllen denn genau so haben wir immer dieses ausgewählt die wir noch eingehen dürfen da wir das wissen können wir das ersetzen durch eben die Summe er aus und einer setzen wir jedes dieser CES durch die Sonnenallergie so dass die ausziehen aus The Erzählern E was haben wir zwar durch gewonnen was wir dadurch gewonnen haben es wenn die Summe umstellen erhalten wir dass das gleich ist die Summe über alle die von 1 bis P TI geschnittene mal y wie denn so auftaucht jedes y i auf das taucht genauso oft auf diesen Tee ist drin ist er noch auftaucht für jedes Element aus aber das die trifft ich einmal y hier in meiner Sommer einfach durch Umstellen dieser Summierung das heißt die 1. Approximation spielte die wir hatten war die 1. Approximation es Aussage war eben wenn es ein 1 war gibt wird ein wenn war größer oder gleich ist ihn geschnitten er hat März einfach T I zum Beispiel für alle E dann gilt dass der Algorithmus eine Approximation so Algorithmus glaube der orginal Algorithmus war 6 13 ein alter Approximation zu Algorithmus bis und ich meine wir haben gesehen dass diese Summe y is das für untere Schranke für unsern optimal wird und hier haben wir jetzt gesehen dass wir den abschätzen können weil wir ja hier das Ganze immer mit Eifer abschätzen können das sozusagen hier das ganze durch Alter abschätzbar ist und das heißt wir gegen eben einfach mal diese y dies und das ist unsere Approximation Scythe das aber nur die Basisversion sozusagen hier und für viele Probleme reicht diese Basisversion nicht weil wir diese Abschätzung nicht machen können die Teddys können größer also größer werden alle zu möchte man Quelltext Text Chasseral Problem muss darum geht es einfach zu überlegen wie finde ich ein paar Ecken die mir die Kantenlänge von meinem die wir die Kantenlänge von meinem Grafen abdecken Na ja jede Kante hat halt nun mal 2 Ecken das heißt alle sind 2 Elemente ich da hab ich jetzt einfach jetzt schon für diese Basisversion ohne laschen ein aber Alter Approximation so Algorithmus in dem Verein 2 Approximation zu Algorithmus allein für die Probleme die uns interessieren die komplizierteren Problem es ist so dass wir diese Abschätzung mich haben wir brauchen besser abschätzen und die Überlegung und da sind wir so ziemlich das letzte Mal stehen geblieben war wenn ich sage na ja als sei er ist das Ergebnis afp von 6 5 2 1 also dieses AF es einfach das Ergebnis dieses Algorithmus mit laschen dann ist jetzt die Frage was ich dafür als als Approximation Scythe beweisen kann was kann ich über diese diese Summe hier im Wesentlichen was kann ich da machen und da hatten wir betrachtet minimale Erweiterungen das heißt es sind solche Mengen zu gegebenem unzulässigen aber solche Mengen B die das sozusagen erweitern und zwar so dass es zulässig wird aber auch so dass ich nicht aus dem die rausnehmen darf so dass es wieder unzulässig wird und die essen und das auszunutzen um einen besseren Approximation Salbe Rhythmus zu beweisen er besser Approximation Skythen zu beweisen so .punkt da sind wir und zwar ist die des folgendes wir gucken uns 14 an also den Leistungs Schritt und wir sind wir konnten uns also an ich J kann nicht gelöscht werden
er hat kann nicht gelöscht werden was heißt das Na ja das heißt das die Menge E 1 bis J Min aus Ahlen die muss unzulässig sein ja denn sonst hätte ich ja er hat laschen dürfen in der Runde dann wird sich aus dass sich jetzt sozusagen rückwärts vor gehe ich weiß genau welche Elemente noch da sind über diesen Aussage treffen muss also E 1 bis E J -minus 1 die darf ich nicht weil die müssen unzulässig sein sonst hätt ich habt ja rauswerfen dürfen das heißt aber auch das wenig also das Ergebnis mit E 1 wisst ihr ob -minus 1 vereinige dann muss das Terminal Augmentierungen sein von dieser Länge hier warum Na ja ich jenem meine stehen ja die drinnen die ich stehen ja die drin die sozusagen diese rasch Runde überlebt haben das sind alle Elemente die sozusagen nach dem Lauf des Algorithmus durch sind ja alle das Flaschen überlebt das heißt aber auch sie sind eben eine minimale Augmentierungen dieser ja unzulässigen Menge nennt die Menge mal B das heißt doch aber auch das für Ali gilt das war es geschnittene CE kleiner gleich B geschnittene CIS wenn ich meine dass wir so konstruiert dass da einfach noch mehr Elemente wir vielleicht später beim Lauschen also diese Menge ist das Ergebnis das Algorithmus das heißt da können auch Elemente aus diesem Teil drin sein die ich hier wirklich neu dazu nehme sind die die mit gelöscht worden sind aber ich nehme nur Elemente dazu die hier auch drin vorkommen können das heißt diese ungleichen gilt offensichtlich sein sagt Nachkonstruktion sagen man lieber so ja also gar nicht dass ich dieses eine Faber und dieses AF offensichtliche Elemente daraus erhalten muss erhalten wird nur noch ein paar mehr dazu bekommt ist klar das war zulässig am Ende also muss es die alle irgendwie treffen es kann sie aber noch öfter treffen damit können ja welche sein die hier noch weg gelöscht werden das heißt aber auch dass wenn ich jetzt später setze auf ich nehmen die maximale immer das Maximum über an die unzulässig sind und ich nehm das Maximum das ist jetzt sozusagen nur noch mal länger geschrieben über alle des ist die minimale Augmentierungen von sind also anders formuliert ich nehme Paare von unzulässigen Mengen an und ihre minimale Augmentierungen her und einfach sage ich schneide das mit Bier und das ist jetzt einfach die Mutationen darüber hat mir auch ein bisschen gesprochen dass dieses TA ist einfach die Menge die jeden 4. ausgewählt wird also T A bezeichnet die Menge aus 4 also wenn ich diese Menge ich in diesen Algorithmus stecke dann werde ich mir irgendwann mal so ne Menge Tee aus die verletzt ist und genau das ist diese Menge die hier drin vorkommt wenn ich jetzt das so nehme aus dem Argument was sich eben hatte dann ist klar dass dieses Ding hier offensichtlich das nach oben abschätzt insbesondere hier kann ich das durch Unwetter ersetzen und kriege das das ganze Ding diese Löschung Variante 1 better Approximation Algorithmus ist man also ich habe jetzt eine bessere Abschätzung gefunden dafür was dieser Algorithmus kann man ja keine approximieren mit Güte Wetter und das schreibe ich jetzt Ersatz ankucken und das Ganze noch mal für das kürzeste Wege Problem an fragen hier die ja ein mehr mehr hatte da würde ich bin doch werden ok was ich eben gesagt habe war Satz 6 17 der eben einfach sagt dass Algorithmus 6 15 ist nein wer Approximation es Algorithmus Schädlings hat und jetzt kommt die Folgerung 6 18 für das kürzeste wegen Problemen können wir das Beta explizit ausrechnen da gilt das Beta 1 das heißt damit dass dieser Algorithmus schon optimal das ist jetzt einfach schon ein Algorithmus der uns DLP-Lösungen also Beweise
dass kürzlich wenn aber unzulässig ist was heißt das Na ja das heißt in unserem Bild der mindestens 2 Komponenten in den dieses zerfällt aber wir haben ja den Start Knoten dann kommt hier irgendwo unsere komischer Graph und ich habe das den Zielknoten es gebe hier mit unserem irgendwie rein das ist irgendwie hier drin und was heißt das Mehr das ist dieser Weg und der Weg ist halt vielleicht hier irgendwie hat so Stöckchen und der zerfällt halt in mindestens 2 Komponenten bei der sonsten durch den Wegfall des nach t hätten wo ja also irgendwo hier hängt der SD drin und hier irgendwo dieses Ding das heißt wir kriegen nur wir kriegen hier induziert Zonen 3 Grafen den mehrere Komponenten zerfällt und leider Frauen eine dieser Komponenten enthält das es und eine enthält das T wer hat das letzte Wort über die minimale verletzt als Regel gesprochen also der Regel nachdem wir diese Telecaster auswählen nämlich dass wir die Inklusion zu minimal wählen und das bedeutet TS wird ausgewählt so wurde wegen minimaler verletzt hat für den jetzt ist aber die folgende Situation klar egal was ich mache irgendwie hier eine Erweiterung zu kriegen von meinem TS sozusagen was ich versuche ist eine minimale Augmentierungen von diesem TS zu finden das heißt die kleinste Möglichkeit wie ich das wieder hoch bekomme ist aber auch klar dass die minimale Augmentierungen die ich hier bekomme Designelemente nicht ja er wird stark verkürzt wo kommen die minimale Erweiterung die wir hier machen wird so aussehen das liegt diesen Schmerz der von TS induziert wird also egal wie ich das jetzt hier außen fortsetze wenn diese Erweiterung minimal ist weil das mal rein egal ich den Weg der fortsetze das letzte des kommt Na ja über diesen handelt der von TS induziert wird über diesen Schnitt geht nur eine Kante dagegen nicht mehr war das Argument es egal wie ich jetzt hier weiter mache ich nicht mit so über 2 hätten zu gehen soll es reicht wenn ich über eine Ecke gehen er kannte man noch das heißt für alle leben wer ist minimal Augmentierungen schon Geld das Geld kann ich mir jetzt hier sparen das D geschnitten mit dem Delta also mit dem Schnitt der von TS induziert wird das das einst ist schreibe des TSC warum man und so mit folgt Better S 1 denn zur Barbetta genau definiert als das Maximum der die alle und damit sind wir hier an der Stelle hat vorwärts der Beweis ist ziemlich ähnlich der jetzt kommt aber davor wollt ich vorher die Frage stellen wer kennt das Minimalkosten aber es Cents Probleme hat das schon mal gesehen keine 0 daher glaub ich überspringe ich diesen Beweis an der Stelle das glaube ich nicht viel bringt wenn ich jetzt erst mal versuchte er sozusagen jeder noch mal den den Grafen theoretischenTeil nachzuholen nur so viel zu dem Problem dass es eine gerichtete Versionen des minimal auf Baum Problems die wir dabei lösen wollen aber ich würde ich empfehlen dass dann einfach an der Stelle im Skript nachzulesen weil wir sonst im Wesentlichen jetzt nur Begriffe machen die zudem wo wir eigentlich hinwollen erstmal nichts beitragen aber es ist eben ein Problem das auch öfter auftaucht als es einem vielleicht gibt es sagen wir so daher gehen wir jetzt machen wir weiter wirklich mit dem Bremer Dual Algorithmen und gehen jetzt wirklich zu Algorithmus 6 20 und die Idee ist jetzt folgende wenn wir uns überlegen wie wir dieser Algorithmus gestrickt immer wenn ich durch die Schleife die such ich mir eine Dual Variable aus und der Höhe die und ein das ist jetzt sozusagen eine Zusatzinformation ist es so die Orakel also die die uns sagen welche Elemente verletzt welche Teilmengen der verletzt sind diese Orakel können einem auf da eigentlich alle Verletzten als zumindest alle minimalen verletzten Mengen liefern mit wenig Zusatzkosten das heißt eigentlich dass es überflüssig sich als immer nur auf 1 EL eine Menge nach der anderen zu konzentrieren eigentlich könnte man in jeder dieser prima duale der Ration viele Dual Variablen hochziehen nicht nur eine und die die es tatsächlich das was nicht nur ein fast sagen weniger Iterationen die etwas wärmer Laufzeiten von dem Problem abschätzt vielleicht interessant wäre sondern es ist sogar so dass diese es simultane erhöhen tatsächlich die Möglichkeit bietet den Algorithmus auch mit in der den Algorithmus auch ne bessere Schranke zu beweisen das heißt die Approximation Scythe dieser Variante ist sogar besser und was im Bild zu sehen ist ist genauso ne simultane Variante des da waren so viele Kreise auch gleich haben das dann einfach die gleichzeitig erhöht worden sind also Algorithmus 6 20 der simultane mal duale Algorithmus und wo also wieder die Schritte 1 2 3 sind genauso wie vorher 10 angleichen wollen war ist die leere Menge und LS 9 nur fangen jetzt an das anders zu machen so lange nicht zulässig bedroht und Ubuntu er natürlich zum 1 Uhr so 5. wird L um 1 erhöht und jetzt betrachte ich in 6. und das ist die Neuerung irgendwie so eine Menge Skript auch da und das Zentrum ist die Menge aller minimalen gerufen verletzten wegen von A einig der treten konzentrier mich eben jetzt nicht mehr auf eine Menge sondern ich konzentriere mich gleich auf mehreren und jetzt das
erhöhen gleichmäßig also alle werden umso sozusagen das gleiche Epsilon wie wir es wollen sie das auch in der letzten Vorlesung für das klassische Primal Dual Verfahren hatten da besteht der Vektor eben jetzt nicht nur aus einer 1 und vielen Nullen sondern eben aus der ganzen Reihe von 1 sind die gleichzeitig erhöht werden für alle es allen während Frau von A es das 1 zu 1 E l gibt so dass eben die Summe über alle es haben wir sie hier genannt da nehmen wir hier wieder alle die Element T e y =ist gleich c e l o 8. Schritt setzen wir aber eben genau Sätze dieses Element e l 1 also und Schritt 10 bis 12 es eben die rückwärts wir vorhin schon hatten UND das ist sozusagen die Herzen der Algorithmus mit dem wir uns den Rest derzeit beschäftigen werden wo es darum geht für diesen Algorithmus der Garantien zu leisten also wir nennen Epsilon J die er hören in der Tat wo also das was sich die EU-Wahl variable nennen das ist halt das sie Orte Epsilon das Epsilon jagt und es ist klar dass Y die für alle ihr lässt sich das y ihr jetzt wie folgt schreiben dass Ypsilanti am Ende meines Algorithmus das ist entstanden durch verschiedener Erhöhung in den einzelnen ja unten das heißt es lässt sich schreiben als die Summe über alle J von 1 bis diese Runde auch immer ich gemacht habe Mehr machen will nicht die Runde sondern wirklich exakt hier in dem alle Art so dass T e also die IT die Menge die hier gehört in unserer verletzt Menge war wenn mal VJ R sie Leute hat also ich hatte gesagt Milliarden Runde möglich alle um Epsilon und das y I am Ende setzt sich natürliche daraus zusammen welchen Runde sozusagen dran war jeder Runde Ostrander wurde so ein bisschen erhöht sehen wir wie gesagt und noch an den Bildern die Kreise werden immer größer die Kreis hier jede Farbe gehört zu einer einzelnen Runde und die Kreise werden immer größer je nachdem in welcher Runde es halt dran war das heißt unsere Ziele .punkt unsere die Funktion mit der wir alles bisher immer abgeschätzt haben die einfach die Summe der y i war die lässt sich jetzt schreiben als eine Summe die die nicht mehr über die ganzen Tag es geht solle die geht es über die Runden des Algorithmus also zeigen die Runde in der jeweils ein Element hinzugefügt wurde indem er nämlich sagt dass ist einfach so oft wie es dran kamen also zahlen umgekehrt so viele Elemente wie Runde dran kamen multipliziert mit Erbsen und J es einfach diese Summation hier umgestellt das oben eingetauscht und dann die Summation vertauscht da ist das heißt insbesondere für diese Kosten von A 1 also unseren Ergebnis am Ende wir wollten das ja abschätzen diese Kosten die lassen sich schreiben als wieder die Summe von ihm gleich 1 bis B aber von geschnitten mit T E y e und jetzt können wir wieder genau die gleiche Summe Summation Informations so Umstellung machen und das ist einfach gleich die Summe überlebt Elemente die ich in meine freien ob beziehungsweise sogar mehr alle Elemente die ich hatte bevor ich gewünscht habe alle Themen die sie im jeden der verletzt als Menge kommen so viel wir davon übriggeblieben sind mal meinen Epsilon out was das hab ich gemacht naja ich hab gesagt diese y wie kann ich dich die Summation da oben ersetzen da kann ich einfach die Epsilon Yards reinbringen und dann kann ich hier meine Summation vertauscht und sagen na ja ich zieh dieses hier in die Summation rein und kriegen genau diese Summe das heißt und das wird unser Ziel sein das Ziel wird sein sehen wir einen da war so das ich diesen Ausdruck dieses TIM Vj wie viele Elemente von der joggten Verletztheit Zwänge bleiben hier sozusagen wie viel Elemente der lauten verletzt als Menge treffen hier mal da das muss ich immer abschätzen können gegen dieses Gamer mal die größte der Größe der Verletzungs Menge also ich schaue mir alle wolle alle Mengen an die hier verletzt habe und so mehrere darüber wie viele dieser Mengen ich in einen Schritt sozusagen hier rein bekommen habe seit ich merke ich bin ab verletzte Mängel wie viele Elemente bleiben am Ende von soner Verletztheit übrig wenn ich das irgendwie abschätzen kann eben ein Anteil dessen wie groß diese verletzt als Mengen Sand dann hab ich ein Gamer Approximation zu Algorithmus mein Ziel es wirklich wenn wir dieses Gamer dass dieser Abschätzung erhalten bleibt sie hatte einen Namen 6 10 ist das glaube ich ich bin ich Ihrer nehmen doch 6 10 ist es aber der Satz den wir damit haben es eben seit 6 zu 20
gut er 21 Algorithmus vor 6 20 ALG Rhythmus 6 20 ist ein Ghana Approximation zu Algorithmus falls Union und ich hätte alle t is nehme den der verletzt Menge von irgendeinem wahr sind und ich jetzt hier über die minimalen Augmentierungen wir natürlich wieder das ich das abschätzen kann gegen Ghana von der verletzt für nach unzulässig und P der minimale Augmentierungen von Haaren also mein Ziel war sozusagen das für diesen komischen Lauf des Algorithmus zu zeigen das reicht aber wird zu überlegen wenn ich irgend verletzte Menge haben ja alle Verletzungen QC Pannen überlege was passiert mit den minimalen Augmentierungen wie groß werden diese minimalen Augmentierungen relativ dazu wie groß die Verletztheit ist wenn ich das gut abschätzen kann dann bin ich im Geschäft und Approximation zu zeigen wie verhält sich das zu den Beta von vorhin bei dem Wetter von vorhin habe sozusagen nicht berücksichtigt dass diese Dinger groß werden können dass diese Verletzung gleichzeitig geben kann und irgendwie klar dass unser Algorithmus damit nicht umgehen kann leider hatte immer nur eine Verletzung nach der anderen betrachtet wenn wir hier so sozusagen alle auf einmal mit betrachten die gerade auftreten alle minimalen Verletzungen und jetzt ist das Ziel 1 etwas spezieller im für eine sehr klare Formen dieses Netzwerk Entwurfs Problem sie Settings hat Problems für leichte Spezialisierung die aber fast alle wichtigen Sachen abdeckt für die zu zeigen dass dieser Algorithmus mit diese mit diesen Gütemaß dass wir das zeigen können dass für die Sachen die uns interessieren dies Ghana mit 2 beschränkt werden kann wer so 1 2 Approximation es Algorythmus erhalten dazu betrachten wir folgende Variante des Settings halb Problems ersetzen wie minimieren wir unser Ziel transponiert Ex und betrachtet sie eben einen Grafen G der hat wieder Knoten Frauen kann er und auch unsere Grundmenge und was ich jetzt gerne hätte ist dass die Summe wenn ich mir alle meine Knoten Menge angucken wenn ich irgendeine kannte aus dem Schnitt hier habe von den E R sein denn es kann auf nicht so viel wieder über die Dixie dann soll das größer gleich sein einer Funktion die von dem es abhängt an sich hab nur Funktion die nämlich erst die geht von allen Teilmengen von Frau nach dem 0 oder 1 und was ich gerne hätte es eben ich betrachte hier ebenso ein klassisches Netzwerk Entwurfs Problem ich will irgendwie ein Netzwerk in meinem Graph habe ich will irgendwelche Teil Grafen haben und wer für welche ich haben will es codiert über diese Funktion f hier die sagt nämlich entweder ich musste bei diesem Schnitt gehen davon 1. induziert wird oder sagt man bei diesen Schnitt da muss keiner kannte drüber geht beim Steiner Baum Problem das wir vorhin hatten ist es eben so dass ich genau sage alle es geben Teile der Damen des enthalten und Teile nicht enthalten die kriegen 1 und alle anderen kriegen wir 0 beim minimal auf spannende Angelegenheit alle nur 1 das ist einfach so wie es ist und die Idee ist hier viel weniger halt auch was sozusagen minimale Verletztheit heißt heißt nämlich sozusagen Mehr solche die die im Inklusion minimal sind solche Mengen 1. und die eben noch 1 sind wir wollen aber jetzt damit dieses Problem nicht irgendwie komisch wird wollen Stelle noch ein paar Bedingungen an dieses F es soll nämlich wie es so schön heißt nicht sein das sind 3 Bedingungen die man stellt einmal in der also die Gesamtmenge sollen mit in Ordnung sein es ist endlich die klar keiner kannte kann 1. Knoten Menge rausgehen wenn ich das hat bin ich sofort unzulässig also brauch ich das hier BFS maximal das ist das Ende nah keine so schöne Bezeichnung aber was sie aus sagte es für alle a b es gilt es die disjunkt sind gilt das und wenn die wenn die beiden Teilmengen ok sind es die Vereinigung auch okay das ist die Kurzform davon also wenn ich hier von A von B habe dass es immer kleiner gleich als das Maximum von 11 von Art und erfahren B das heißt da ich ja weniger Bedingungen haben wenn man F 0 ist eine Teilmenge heißt das wenn ich 2 disjunkte Mengen die irgendwie zusammen Tour dann wird das höchstens besser es wird nicht schlechter werden dadurch also irgendwie klar Sensornetzwerken Force Problem es geht ja darum dass wir sagen wir müssen da son Schnitt drüber welche 2 Mengen zusammen tue damit sozusagen die den Stich Schnitte kleiner mache dann sollte das irgendwie netter sein und die Bedingung zu sehen die Quetschies jetzt hier noch so hin der symmetrisch das ist auch irgendwie da werde über Schnitte Reben auch irgendwie klar wenn ich eine Menge haben sich die Gruppe den Schnitt an dann ist das ja der gleiche schnitt das würd ich mir die andere Menge angucken wenn jetzt gerichtet sind und da hätte ich gerne das bitte erfahren erst das gleiche ist wie er von Frau oder es insgesamt sind das relativ schwache Bedingung wenn man sozusagen die Intuition die dahinter steckt hat wenn man sagt es soll halt eben mit der
Schnittbedingungen in dem Grafen sein dann sind das relativ natürliche Förderung ist klar ich komme nicht raus aus dem Ding es ist auch klar im Schnitt wird sozusagen der einfacher zu erfüllende Bedingung sei ein wenig 2 Mengen zusammen und es ist auch klar der Schnitt ändert sich halt nicht wenn dieses Kompliment nehme von den Knoten Mehr und wenn ich jetzt die was wir jetzt machen werden es uns angucken wie sieht jetzt die Bedingungen die wir erfüllen müssen um seit 6 21 zu kriegen Sie denn dem Spezialfall aus dass unser Problem diese spezielle Form hat und dann versuchen wir es zu zeigen dass wir dafür 2 Approximation es Algorithmus kriegen fragen so weit .punkt das heißt er wer wir kann er ich bin also neues Ziel kann wie lautet die Umformulierung dessen was wir da gerade haben ja das heißt wir sagen wir summieren überall wir wollen zeigen dass die Summe über alle verletzt Mengen von Art wobei wieder unzulässig und minimale Augmentierungen es das die Größe des Schnittes von P vom 1. kleiner gleich 2 mal der Größe der Verletztheit Menge ist ich werde das sein aber ein Problem hatten wir vorhin das einfache ebenso wir gesehen hatten ich will sozusagen dass diese Funktion erst so gestrickt dass das sie haben Wellenlängen trennt ja es gibt ein Problem das hat mir etwas kompliziertere das ist das sogenannte tief neuen Problemen das sie dessen etwas künstlich aus es wird aber benutzt wenn man zum Beispiel sogenannte Jay niest Brust Mentoren ausrechnen will also Touren durch einen Grafen so dass alle Kanten getroffen werden von dem Grafen also nicht unterwegs hält man wo man alle Knoten treffen will seine leben alle Kanten des der Reben die Analogie zu einem Hausbooten da reicht es halt nicht dass der Postbote alle Straßenkreuzung erwischt sondern er soll gefälligst jede Straßenseite werden bitte abgelaufen daher eben das Ausbooten Probleme und den wesentlichen dieses Titan Problem hatten etwas kompliziertere Funktion f ich würde ich vorschlagen die einfach nachzulesen stattdessen kümmern wir uns jetzt um ein mal was wir brauchen um zu charakterisieren was sozusagen diese echten Funktionen für Eigenschaften haben bzw. was das für Zulässigkeit und Unzulässigkeit bedeutet also zulässig also 11 ist immer echt aber zulässig ist genau dann wenn für alle CCS eine zusammenhängende Komponente von nämlich von geht kann dauern sondern fahren so wobei ich eben als Kantenlänge genau diese zulässige Menge an nehme dass ich betrachte meine Knoten Menge Frau nehme genau die kann nicht ausgewählt habe und betrachte jetzt alle zusammenhängenden Komponenten in dem was ich da drin habe für die muss gelten erfahren Sie es neue und das auch irgendwie klar denn was die Bedingungen sagt was er die die Nebenbedingungen man die Pille sagen es immer wenn das F 1 ist dann brauche ich diesen Schnitt noch dann muss ich aus dieser Menge rausgeben ja aber dann werden sie keine zusammenhängende Komponente weil ich könnte 10 auch einfach vergrößern zum entweder ist nicht zulässig dann geht da kein Schnee doch aus dann darf das aber nicht 1 gewesen sein sonst wärs ja nicht zulässig oder ist es neue dann geht auch nicht raus aber ich brauche ja auch nichts dass daraus geht und die Variante B es ist ist minimal verletzt 3. .punkt nein hatte und nicht er selber sondern die minimal verletzten man waren so rum also die die als versprach die die von verletzt werden suchen die sind die zusammenhängen Komponenten C schon wieder den von induzierten Teil Grafen mehr wird ein
.punkt erfahren Sie gleich 1 also ist es klar dass diese Mengen Seale verletzt sind in der Nähe von CS 1 und sie sind lebende Zusammenhänge Komponente in meinem induzierten Teil trafen die Frage ist nur sind Sie da eben auch maximal und sind das sozusagen die einzigen müssen verletzte minimal verletzte Menge immer zusammenhängend das ist was wir beweisen müssen also Beweis es verletzt von A und erfahren es ist 1 sonst wäre es nicht verletzt sonst kann man es einfach nicht verletzen und und der Schnitt in dem von induzierten Teil Grafen von der S der sei leer also der von S induzierte schnitten dem von induzierten Teil Grafen der ist sozusagen leer es gilt dass es sich schreiben lässt als nur Vereinigungen vor irgendwelchen zusammen nur hängen Komponenten CI nein also klar es selber als irgendein Graph und er und das lässt sich halt schreiben irgendwelche Komponenten und da etwa bei maximales heißt vereinigen macht das Ganze nicht schlimmer existiert ein die Welt erst von C E =ist gleich 1 vereinigen war dass er genau die maximal lität Eigenschaft vereinigen macht das Ganze nicht schlimmer also muss es ein CI gegeben haben wo das ganze 1 ist da es aber C E verletzt und das ist unser widersprochen den Ermittlern des die Menge der betrachte dann einfach nicht minimal und damit war denn auch das ist eben immer eine verletzte Menge sein muss die deshalb in eine Zusammenhänge Komponente sein muss die verletzt ist n was wir jetzt machen ist wir schreiben doch mal diese maximal Lizenzbedingung anders und zwar dafür dass immer dann wenn die man wenn das Ding symmetrisch ist also wer mal 6 25 11 symmetrisch dann es eben es maximal genau dann wenn es komplementär wo kann ich und es komplementär bedeutet eben dass für alle er es war und es osv gilt das wenn ich schreiben kann als enthalten es ist enthalten EN V und es gilt von als er von der SS gleich 0 dann folgt schon das und so ne Art auch 0 ist also wenn ich so ein Schlachtung hier habe und ich sehe die beiden sind nur dann muss auch das Komplement schon 0 sein sozusagen etwas Spezialisierung von dem was wir vorhin auch schon hatten mit der symmetrischen Eigenschaft dem beweisen ,komma es relativ direkt einfach aus den Definitionen und führt uns ein bisschen jetzt wieder auf vornehmen von den ganzen weg das sorgt also kommt jetzt der Beweis von Satz 6 26 n hoffen wir dass wir damit durchkommen wenn dann das ist sozusagen nämlich dann der natürlich Abschluss prima Dual Algorithmen Quelle würde für oder mehr also seit 6 26 Algorithmus 6 20 ist ein 2 Approximation es Algorithmus für 6 12. das das Programm da oben das war diese neue Formulierung des Settings hat Problems .punkt falls 11 geboten dort er ist und also so war es als
unzulässig wir betrachten Mehr die verletzt die Mini die Verletzten in dem die minimal verletzt von dem die oben schreibe wir einfach mal Dan gilt .punkt das hat uns gerade nehme er mal überlegt er S gleich 1 für alle wenn die von verletzt werden alle Mengen die von verletzt werden für die gilt er von 1. 1 sein und die mal wieder so minimaler Augmentierungen Uhu und wir betrachten wenn .punkt denn von B induzierten der 1 Grad das heißt die ist jetzt etwas was zulässig ist für unsere Ursprungs Problem unter unserem Grafen darauf eingeschränkt also wir können uns das sie in dem Band vorstellen behandelt werden so umbauen damit zu sein man auf einem Baum gehabt in dem Bau der Seidel in der Erweiterung von dieser Menge an das heißt es muss gar nicht mal Baum sein der kann auch ich geraten ist minimal also muss warm sein und was wir jetzt machen es wir vereinfachen diesen Grafen wir kontrahieren nun gegen diesen Grafen ich nenne mal kurz geht dem mal in einen schlauen nahm der noch nicht verbraten ist n der Beginn der nach also wir neben diesen Grafen was jetzt machen es wie kontrahieren das heißt wir ziehen die Kanten zusammen und ziehen die Knoten zusammen fahren einen zusammenhängenden Teilmengen von unserm Ursprungs Grafen VA also das heißt wir müssen uns das so vorstellen wir hatten hier irgendwelche Knoten und die Bahn schon irgendwie in unserem Art verbunden dass er meinetwegen so war es der und dann kam das P und hat hier noch bekannter eingezogen und dann sieht unser neuer Graph so aus dass wir einfach sagen das Ding wird ein Knoten und das Ding wird ein Knoten die Kante behalten wir und diesen Grafen nach Kontraktion denn nennen wir ha sind die neuen Knoten und F sind die neuen kann und aus der minimale lität ist klar das von 11 ist Einfalt und es gibt nur 1 zu 1 Beziehung zwischen F und kannten aus D ohne das muss ich finds Grafen konstruiert von dem wir wissen wir aus wie das sinnlichen Wald der jetzt einfach sehr stark die Struktur dieser Erweiterung kodiert wir wissen einfach die kannten dieses neuen Grafen sind genau die Kanten der Augmentierungen dazukam ein und nun gilt das für jeden neuen Knoten Kraushaar der ein so Zusammenhangs Komponente es von in den Sinn der SV liegt und zwar jetzt eben die es von VA also nehmen wir einen Knoten in unserem neuen Grafen und der liegt halt jetzt irgendwie der zugehörigen der Cook und die zugehörige Komponente an an dann gilt gerade dass der Grad dieses Knoten im 1. dieser gewahrt der ist in HR der ist gerade die Größe des von P induzierten Schmerz an dieser Kante in diesem von dieser dass gerade die Größe des schätzt dass in dem vom BMU zierten Grafen und der Schnitt das Leben von SV induziert und lohnen es ist eine wurden nein eben setzen wir leben definieren und zwar so dass gilt Frau aber ist genau alle Komponenten Frauen verletzten Knoten also ich gucke mir jetzt ich in die Ziele ja einfach diese Knoten in meinem neuen Grafen und gucke mir einfach die die Verletzten Teilmengen an und die Knoten die zu diesen verletzten Teilmengen gehören die männliche W und der Welt das zusammentun und sehen wir wissen jetzt was ist sozusagen bedeutet dass hier was dieser Grad in den neuen des Grafen bedeutet und wir wissen was sozusagen diese Knoten Menge wie die ist die uns eigentlich interessiert dann sehen man dass die Summe über alle Wege aus diesem W und den Grad über diese Dinge das das gerade kleiner gleich sein muss zweimal diese sowie damit wir zeigen können was wir wollen also zu zeigen ist genau orten das das wollen wir wir haben einfach jetzt oh Wunder korrigiert das was sozusagen wir diesen was in unserm alten Grafen was die Augmentierungen macht an den Eigenschaften dieses neuen des Grafen kodiert und das einzige was wir wirklich zeigen müssen es ist und ich dir zu zu einem Beweis 1 drüber wenn wir zeigen können das alle Blätter in diesen neuen Grafen HF wenn wir zeigen können dass alle Blätter es gibt genau diese
Blätter fällt das wir für alle Blätter haben dass die verletzt wird alle Blätter sind verletzt wenn müssen nur das zeigen wir zeigen können alle Blätter sind verletzt dann sind wir fertig denn wenn wir sagen können alle Blätter aus H a f sind im Web dann Geld einfach die Summe für B aus W sie erfahren W die kann ich doch einfach abschätzen erstmal Sie es gleich als die Summe ja aller es erstmal gleich der Differenz der Summe aller gerade die Summe aller gerade man aus die Summe aller die nicht wir sind das 1. Mal einfach nur umgeschrieben das W und in das Insee sein und nicht im Wege sein einfach genauer genau zusammen den ganzen Grafen ergibt dann ist es doch aber so dass ich diese Dinge die hier nicht dran sind der Pferde und weiß ich dass sie für alle Dinge weil ich weiß dass ich den Bereich habe in meinem Haar und Wälder haben ja nun mal die Eigenschaft dass sie nicht mehr als kann -minus 1 kannten nicht weniger als ich mehr als Knoten Zahl -minus 1 Kanten haben also weiß ich dass die Summe aller gerade zusammen nicht mehr sein kann als zweimal -minus 1 weil ich ja jeder kannte jeden K jede Kante genauer einmal Zelle das heißt jeden Knoten hier drin selig doppelt aber ich weiß auch dass diese Dinge die nicht anwesend die müssen alle mindestens Grad 2 gehabt haben das heißt dass hier kann ich auch mehr einfach anschauen als das ist -minus 2 Mal Größe von an -minus Größe von W und wenn ich das zusammentun dann hab ich gleich das das ganze hat gleich zweimal je -minus 2 ist und das genau besser sogar als das was ich zeigen wollte das heißt dass wir übrig bleibt zu zeigen ist einfach je das lacht ist jedes Blatt von meinem des Grafen wird von verletzt wer sich auf die Uhr sehr dass wir sozusagen der derzeit 10. ich mir ist relativ gleich ob wir das jetzt machen oder das dann beim nächsten Mal noch sieht oder bis ich selber anguckt weiß nicht was Eure Präferenz ist aber dennoch setzt machen es zu also zu zeigen alle Blätter aber es war es haben die Eigenschaft das er von alle Blätter Frau aus das erfahren es Frau gleich 1 geht wer wie sieht das aus das sieht doch so aus dass ich mir irgendwie so mein Wald machen dann habe ich hier nein Knoten der hat genau eine kannte er an der dranhängt hängt noch irgendwas dran wir hängt noch irgendwas dran und ich bin mir meine Gesamtzusammenhangs Komponente C zulässig gewesen also Geld erfahren Sie gleich 0 ich will aber zeigen dass dieses 1. von Frau mit dass das 1 ist also angenommen Helfern SVS Nolte Na ja wenn das der Fall ist dann folgt das und sollen wir auch das ist 6 25 das 11 Frauen C dieser Komponente ohne SV dass es muss auch 0 sein das war die Komplementarität Eigenschaft die wir vorhin hatten dabei ist ja da wird B minimal war heißt es dem minimal daraus folgt die ohne Ehe es soll zulässig das war klar wer mehr B so gewählt dass es gerade noch minimal zulässig war so weit ich eine Kante solch ein Element aus per raus also zum Beispiel dieses hier da muss es unzulässig werden nun ist es aber so dass wir alle 6 24 hatten wenn ich hier ne des von Animal verletzt Mengen an angucken dann muss das Ganze heißen dass entweder dieses hier das verletzte Menge war oder wird er da ich über Zusammenhangs Komponenten Rede muss dieser Teil verletzt gewesen sein also das ist verletzt sobald ich die Kante rausnehme zerlege ich meinen sie Zeuge müssen Sie mal zerlege ich meinen 10. 2. Zusammenhangs Komponenten wenig einmal dieses V hier und da einmal den ganzen Rest damit ist mit sag ich aber dass es unzulässig dieser Rest hier der zulässig behaupte ich werde aber unzulässig ist na dann heißt das dieses Teil hier muss 1 gewesen sein das heißt aber auch dass hier muss 1 gewesen sein dieses F 4 und da hab ich mir gerade überlegt wenn das Nullen war er das hier oben nur war dann muss auch das wohl gewesen sein das heißt eine der beiden Sachen muss darf nicht nur gewesen sein und das es Widerspruch zu der andern und damit wenn wir fertig kann
Netzwerk <Graphentheorie>
Klasse <Mathematik>
Besprechung/Interview
Ausgleichsrechnung
Diskrete Optimierung
Computeranimation
Ebene
Einfach zusammenhängender Raum
Nebenbedingung
Untere Schranke
Zusammenhang <Mathematik>
Gewicht <Mathematik>
Reihe
Kante
Element <Mathematik>
Zahl
Dualität
Spannender Baum
Teilmenge
Summe
Variable
Menge
Verallgemeinerung
Rundung
Ausgleichsrechnung
Vorlesung/Konferenz
Zielfunktion
EUKLID <Programm>
Schnitt <Mathematik>
Graphentheorie
Erweiterung
Untere Schranke
Momentenproblem
Reihe
Kante
Zahl
Ganzzahlige Lösung
Spannender Baum
Summe
Variable
Menge
Stella, Tilemann
Abschätzung
Vorlesung/Konferenz
Ecke
Leistung <Physik>
Einfach zusammenhängender Raum
Erweiterung
Länge
Graph
Extrempunkt
Betafunktion
Laufzeit
Iteration
Maximum
Kante
Zeitzone
Teilmenge
Variable
Menge
Rundung
Höhe
Abschätzung
Vorlesung/Konferenz
Inklusion <Mathematik>
Schnitt <Mathematik>
Ecke
Kreis
Summe
Menge
Spieltheorie
Rundung
Reihe
Abschätzung
Vorlesung/Konferenz
Vektor
Null
Algebraisches Modell
Einfach zusammenhängender Raum
Nebenbedingung
Zusammenhang <Mathematik>
Graph
Betafunktion
Maximum
Kante
Teilmenge
Summe
Menge
Homogenes Polynom
Vorlesung/Konferenz
Schnitt <Mathematik>
Inklusion <Mathematik>
Funktion <Mathematik>
Einfach zusammenhängender Raum
Algebraisch abgeschlossener Körper
Erweiterung
Komplementarität
Zusammenhang <Mathematik>
Graph
Formation <Mathematik>
Kante
Gleitendes Mittel
Gradient
Teilmenge
Summe
Menge
Seidel
Vorlesung/Konferenz
Schnitt <Mathematik>
Einfach zusammenhängender Raum
Summe
Komplementarität
Zusammenhang <Mathematik>
Wald <Graphentheorie>
Menge
Vorlesung/Konferenz
Kante
Zahl
Gradient
Null

Metadaten

Formale Metadaten

Titel Primal-Dual-Approximationsalgorithmen II
Serientitel Diskrete Optimierung (Optimierung II)
Teil 24
Anzahl der Teile 26
Autor Schewe, Lars
Martin, Alexander
Lizenz CC-Namensnennung - keine kommerzielle Nutzung - Weitergabe unter gleichen Bedingungen 3.0 Deutschland:
Sie dürfen das Werk bzw. den Inhalt zu jedem legalen und nicht-kommerziellen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen und das Werk bzw. diesen Inhalt auch in veränderter Form nur unter den Bedingungen dieser Lizenz weitergeben.
DOI 10.5446/31792
Herausgeber Technische Universität Darmstadt
Erscheinungsjahr 2009
Sprache Deutsch

Inhaltliche Metadaten

Fachgebiet Mathematik

Ähnliche Filme

Loading...