Merken

Primal-Dual-Approximationsalgorithmen I

Zitierlink des Filmsegments
Embed Code

Automatisierte Medienanalyse

Beta
Erkannte Entitäten
Sprachtranskript
nur in jene höre vom Mhm ok damit ein schönen Tag
heute vertrete ich die Vorlesung wir das vielleicht bemerkt hat dass er diese auch Mittwoch noch mal tun unter dem ist mit 10 heute Primal Dual Approximation zu Algorithmen was ihr das letzte Mal gesehen hat war ein normiert Heime Proxy nächstens geben für das Schnappsack Problem anders formuliert wir können in relativ kurzer Zeit das Land seit Problemen ist aus Erzählungen approximieren heute werden wir eine ganze Reihe von Problemen beziehungsweise heute und das nächste Mal wenn für ganze Reihe von Problemen Approximation Fall gut man kein mit der festen Güte sie je nach Problem relativ gut relativ schlecht wäre dieser Wahlen ein sehr großes übergreifenden in einen sehr großen übergreifenden Rahmen passen lassen nämlich eben als Primal Dual Algorithmus da noch relativ viel Zeit dann bis Ende des Semesters ist verglichen zu dem was noch kommt ich anfangen mit erstmal die klassische Variante von Primal Dual Algorithmen sowie die nicht den Script vorkommen erstmal vorzustellen und ist die Idee zu geben wie man überhaupt auf die Idee kommen sowas zu machen wie man es da macht also ich fange an mit klassischen Primal Dual Algorithmen klassisch bezieht sich in dem Fall darauf das nachdem Leute angefangen hatten 1. kombinatorische Algorithmen für Probleme und das Verein jetzt mehr dass der Algorithmus von fordern Falke sind für das Maxtor Problem zu nennen nachdem sich die angeguckt haben haben sie versucht zu überlegen kann ich das nicht verallgemeinern kann ich das nicht in einem allgemeineren Rahmen bringt und das 1. was Leute da gemacht haben war was Danzig vor dem Volke wohnen in einer relativ frühen Arbeit gemacht haben wenn ich das versucht zu verallgemeinern darauf dass man gewisse Sorten von Lernprogrammen exakt löst also das heißt wir werden jetzt uns gleich anschauen praktischen anderen Algorithmus um lineare Programme zu lösen wenn im 2. Schritt der danach kommt wird es eben sein dass wir uns diesen Algorithmus ansehen oder dieses Muster für mehrere Algorithmen und ein bisschen modifizieren um eben für unser ganzzahliges Programm gute Approximation zu bekommen dabei wird uns immer helfen dass wir es so und wenn man diesen Willen am Programm auch orientieren und uns das dann auch gleich die Güte Garantie besser sagt die Abschätzung für die Güte Garantie liefert also der klassische Fall ist wir fahren mit dem linearen Programm an uns wahrscheinlich das in der Form minimiere C transponiert x a x größer gleich B und X größer gleich 0 und das soll mein prima das Programm sein jetzt wo ich mir das dazu duale Programm an und das ist maximiere wir transponiert y a transponiert y ist kleiner gleich 10 und y ist größer gleich 0 nicht dass wir was wie sie anfangs noch gut und es ist ein duales Programm und jetzt als Intuition ist wir müssen mal dafür wir sollten mal davon ausgeht damit man sowie bekommt warum das was jetzt kommt sinnvoll ist siehst du alle Programme ist meistens wir sehr einfach von seiner Struktur her insbesondere ist ist schnell kann man schnell zulässige Lösung dafür finden man wenn man zum Beispiel dieser Komponenten Vektor c hätte nur positive Einträge dann sehen wir dass hier Zulässigkeit zu bekommen sehr einfach ist weil der 0 automatisch zulässig ist wenn sofort unzulässigen Startpunkt für das Ding und die wir schon mal waren wäre dann hätte ich das gelöst na ich hätte es gelöst wenn ich einmal wenn ich den kommt wir die Bedingungen von komplementären Schlupf es sollte das heißt wenn ich der sie jetzt angucken seine bei den Trimaran geschluckt wenn ich weiß dass XJ größer nun ist wenn ich hier irgendwie Annex J habe das größer 0 ist dann impliziert das sofort das wie ich an der Schranke sein müssen also das gut mir gerade mal sicherheitshalber das stellt jetzt das also wenn ich mir die Jatte Zeile von diesen ganzen Kram der an Kurköln das das hier an der Schranke ist das bejahrte Eintrag dieses Vektors soll CO 2 das heißt ich kann mich hier auf die alte Zeile von diesem den beschränkt und wir machen das oder wenn uns das vielleicht auch noch mal Notation überlegen wie wir nämlich sagen so ne Menge Yard und sie besteht genau aus dem die Art wo sozusagen diese Bedingung offensichtlich erfüllt es nämlich die WHO Adtranz wo die je Zeile genau gleich C Art ja das sind die Bedingungen oder private Schlumpf offensichtlich erfüllt und genau so dieser allen komplementären Schlupf der mir sagt wenn das Y hier größer als 0 ist dann muss ich hier aktiv sein er muss hier die Gleichheit sein ja damit das Thema wenn also y neues dann impliziert das ist in der IT in Zeile von Aix das das grade W i s t und das wirklich ne Menge I 1 wo eben diese Bedingung auch offensichtlich erfüllt ist also was ich gemacht habe ist jetzt erstmal nur wiederholen was in unserer Optimalität Bedingungen da haben wir einmal den Trimaran komplementären schon von einer dem dualen komplementären schluckt und ich hab Mutation dafür eingeführt ich hab gesagt wir haben hier die Variablen bei den offensichtlich die Bedingung erfüllt das und werden wir die Variablen bei dem die offensichtlich erfüllt ist und die Ideen und von der dualen Verfahren ist zu sagen wir schauen uns Lösung von globalen Problemen an und schaue mir an was sagt das über meine Bedingung vom prima Schlupf die sagt doch wenn ich hier irgendwie meine Lösung habe und hier bin ich nicht an der Schranke wenn ich also sozusagen transponiert y kleiner als C habe für irgendeinen J mehr da muss man liegt ja schon 0 sein sonst verletzt nicht aus das heißt ich kann meinen kümmern dass wenn ich jetzt versuche ne prima Lösung zu finden kann ich trifft kann es Westindien nämlich sagen ja ich hatte eine duale Lösung da guck ich wie Ypsilons an wenn ich feststelle da sind welche wo ich hier nicht an der Schranke bin dann kann ich die oben wenn ich das lösen will alle auf 0 setzen das wird dann unzulässig sein und dann ist die Frage wenn ich noch nicht optimal werden wenn ich jetzt unzulässig bin wie lange ich jetzt dieser Unzulässigkeit warf darunter wichtige war Lösung ändert rein formal kann man das über das Prager Firma machen weil wir nun ein bisschen mehr helfen dass das algorithmisch irgendwie klarer wird wie man da jetzt vorankommt
und die Ideen und wir machen ein restringiert es prima das Problem also wir streng unser prima das Problem ein unter der Bedingung dass sich eine duale Lösung hab ich hab eine duale so ganz konkret gegeben sei es eben wie das überall 0 sind wird streng dich mein Primar das Problem ein er sich schon in restringiert das Bremer das Problem an und dieses restringierten Primaner alle Problem hat dann folgende Form na ja ich sage Aix jetzt jeweils kann ich mich der ja auch sozusagen Zeilen einschränken also die jede Zeile von dem X also jede Zeile von multipliziert mit x die muss größer gleich waren das hatten wir einfach schon das war ja genau das überhaupt hier mal zulässig werden und zwar fordern wir dass für alle die sich im also wenn und seine wenigen übrigen duale Lösung haben wir konnten uns den Dual die dualen 4. Bedingungen an und sagen na ja wenn das y hier größer 0 das dann weiß ich muss das mit Gleichheit gelten das heißt sie muss kann ich einfach das fordern und muss weder jetzt dort habe glaub ich gerade kurz innehalten wir haben hat eine sind wie einer also ich hab sind kurz eine Änderung hat viel Sonne angenommen wir müssen hier die mit Definition von diesem I leider ändern er hat ist nämlich leider falsch im Ort wir setzen wir diesen die Definition von dem i anders an als ich das gerade mal in meiner Geschwindigkeit gemacht habe wir setzen die so an dass wir hier nur die reine nehmen und das hier nicht erfüllt ist fertig jetzt aus Versehen gerade überschlagen also wir setzen dass wir so ein hier sind gerade die is drin Uetze die 0 ist das heißt insbesondere das sind die es wo man Sie hier auch nicht Gleichheit haben muss das sind die ist wo man nicht gleich alt haben muss das heißt hier darf ich diese Bedingung einfach so schreiben dann stimmt mich auch wieder mit dem was ich jetzt sage hier dass ich diese Bedingung so schreiben da weiß ich mein y das vom Einflusssphäre hab ich hier keine Einschränkung was ich jetzt mache ist ich sage mehr für die wo ich aber eine Einschränkung habe dass ich Netzwerk ein das sind die die nicht in den Miesen dafür hab ich nur Einschränkung durch meinen dualen Flop das sich jenes Werk variabler ein und was ich jetzt mache erst ich gebe Ihnen neue Zielfunktion für diese Frist prämierte Primal ich gehe hin und sage minimieren Mehr einmal bin ich seit 4 also ich will so wenig wie möglich seit Jahren und zum anderen hätte ich gerne für Alex für alle ihr habt wo jeder keine Gleichheit angenommen wird das sollen gefälligst die X möglichst klein werden was eben genau meine prima Schlupf Bedingung ist also ich erlaube jetzt rein formal das meine Flugbedingungen verletzt werden und die praktisch als Bestrafung in die Zielfunktion rein er sich haben Elke in das ist zulässig so ist es konstruiert wenn ich den zulässigen duale Lösung hat aber ich bestrafen wenn ich hier flog Farbe und ich will jetzt versuchen möglichst wenig Schutz zu bekommen insbesondere wenn ich jetzt hier dieses Problem und einfach 0 als der Funktionswert bekomme damit ich hart ist weil ich dann weiß ich habe eine Lösung gefunden wo das hier nur ist das heißt wo keinerlei Slag mehr vorhanden ist insbesondere wo diese beiden Bedingungen erfüllt sind und das war mein Optimalität Kriterium für Primal und Dual das heißt welche so X-Finder das das erfüllt bin ich von Kate ist das halte ich hab jetzt dieses LP durch dieses LP ersetzt und muss kann es eine ganze Reihe von diesen Dingern lösen was wird mir das bringt das bringt mir nur dann was wenn einer Hauptprobe mein Hauptproblem in dem See lag denn das braucht ja nicht mehr auf ich hab das sie verschwinden lassen und den vielen der Probleme die wir die die wir uns begegnen werden es ist einfach so dass bildende zulässige Lösung finden verhältnismäßig einfach ist aber der eigentliche die eigentliche Schwierigkeit durch das C reinkommt also Beispiel was gleich sehen werden ist das kürzeste Wege Problem zu entscheiden ob es irgendwie einen Weg von A nach B gibt das ist meistens einfach aber zu entscheiden das ist der kürzeste ist es schwierig verhältnismäßig aber hier müssen wir nur entscheiden ob wir hier zulässig sind mit einer gewissen Größe die halt in diesen Flachs liegt das heißt das machen werden dass wir werden unser schwieriges Problem versuchen einfach zu machen dadurch dass wir dieses C haben verschwinden lassen aber noch ganz sind wir nicht mit der LP mit der LP um Schreiberei fertig was jetzt kommt ist die ob und wie sich das gehört das duale zum restringierten prima Wahlen an also Kriege machen LP außer dass das hinkriegen das duale zudem restringierten prima in dafür brauchen jetzt es sei Blödsinn und spricht und das sieht erst fast so aus wenn ich das hier strikt einfach dualisierte kriegen wir hier wie transponiert von unserm y strich wir kriegen für alle J aus Art ganz normal die Bedingung also y transponiert jobbte Zeile davon y strich das soll kleiner gleich 0 sein denn hier zu Yards zu den X Yards im Jahrzehnt gibt es keinen gibt es keine Werte der Zielfunktion also kriegen wir das hier was ich noch Krieges zu allen anderen Lords die den dem York während kriecht das muss kleiner gleich 1 sein denn hier ist der Funktionswert 1 und wenn ich mir angucke was noch mit denen was ich noch zusätzlich kriege das ich kriege das jedes y e sprich größer gleich Min aus einem sein muss wenn ihm wenn ich nicht in ihren und y ihn muss größer gleich 0 sein wenn die aus die das ist jetzt vom mal hier einfach die Bedingungen die wir haben tualisiert und eben gedacht dass wir exakt J das sozusagen die über die Yards gehen und die es gehen über die I und daraus das bewusst uns dann sie unsere Bedingungen herleiten und jetzt ist sozusagen auch relativ klar was passiert wenn wir dieses
restringierter Female nicht lösen kann ist also nicht lösen wir können's in anderen aber nicht lösen können und der Funktionswerte sehr positiv wer den Funktionswert hier echt positiv dann ist auch dieser 10 Funktionswert hier ist positiv was wird wird überlegen müssen was das genau dieses y strich dann so konstruiert ist dass ich meine duale Lösung im ursprünglichen abdecken kann also was ich jetzt machen wenn es ich will sagen setzte unser y 2 ,komma unsere neue Primal unsere neue Dual Lösung pardon an als das Y was wir schon haben bloß Mädchen an +plus Ärzte waren von diesem y spricht also was ich gerne hätte dass ich hätte gerne y 2 sprich ist unser y +plus etliche mal diesen y strich die Frage ist jetzt und was ist gerne hätte ist das eben B transponiert y 2 größer gleich nein sogar echt größer hätt ich das gerne als B transponiert y und die Frage ist wie Krieg ich das jetzt sehen als ich habe meine y spricht das löst der AP und die Frage ist wie konstruiere ich mir jetzt daraus eine neue Lösung Na ja da nicht dass es das hier nur das kann ich mir folgendes überlegen wenn ich mir diese Bedingung angucke ich sage das Elbstadt transponiert Ärzte sollen soll immer kleiner gleich C sein dann ist doch klar dass für alle Yard aus die einzige Beschränkung ist dass ich hier wenig ihr dieses y sprich habe das wo diese Zeile kleiner gleich 0 wird da bewege ich mich ja nur weg fallen der Schranke die hier aufgedrückt wird seit das einzige was mir passieren kann ist dass ich mein y zu klein mache ja weil wir den dort aus Jork setzt sich hier um eine Schranke und ich sage na ja mehr als weg die hier muss ich mich automatisch weg bewegen weil das den kleiner gleich 0 ist also entweder bleibe ich einmal Schranke oder ich die runter das heißt hier bei den y j aus die Orte ist klar es muss immer größer einfach nur aufpassen dass man y nicht mein y dort nicht unter die 0 runterfällt bei sehen hier wo ich noch den J nicht aus J da bin ich noch nicht an der Franke da bin ich echt kleiner als die Schranke das heißt dann darf ich mich n Stück rauf bewegen und das einzige was wir da passieren kann ist dass ich nicht zu viel auf den Weg und da muss ich halt gucken um wie viel darf ich mein Epsilon hoch bewegen und eine nicht einfach von allen diesen Ärzte Bedingungen ich der jeweils kriegen nämlich einfach das kleinstmögliche Erzählung also schreiben wir das mal formal aus also wir kucken aus dem wir sehen wegen Definition von den I ja das und sagte dass die gleich 0 sind genau wer ihr 1. nie es klar y 2 Strich wird größer gleich 0 sein werden ja das Erzählern kleiner gleich dem man ja optisch nicht aus J und transponiert Jahrte Zeile y ist größer als 0 wenn wir da das Minimum sowie ein das sie J -minus aber transponiert ja zu Zeiler y durch Al transformiert ja y strich also was heißt das noch mal sprich das ist im Wesentlichen die eine Bedingung ich gerade gesagt habe nur nochmal formal geschrieben wir gucken uns an wenn man dort nicht aus dem große hat war dann saß ich noch nicht an der Schranke und ich darf man y strich entsprechen meinen y 2 Strich entsprechend erhöhen und wie weit darf nicht erhöhen 1 bis ich an die Schranke stoße und das ist einfach genau die Bedingungen ich noch mein geschrieben hat als ich erhöhen jetzt meine Zeeland 2 Strich um dieses y strich also mit dem 1 zu 1 die Rätsel Lammerts Landstrich draußen das erzählen darf ich höchstens so groß werden dass ich hier an so eine Schranke Lauf und ist Größe ab wir einfach nochmal formal hingeschrieben damit klar ist was da passiert Na hier ist noch J 2 und die andere Bedingung ist halt ich darf nicht kleiner werden als 0 also wegen Definition von ihr jetzt mal wirklich ist wegen der Definition von I ist klar dass eine Art verloren kleiner gleich auch wieder eine Minimum und zwar diesmal jetzt eben den Minimum Minimum über alle Ideen nicht denn diese so dass diese 4 auch kleiner als 0 5 und dann eben kriege ich einfach -minus 14 lagen die durch y spricht von mir also ich kann hier ja und gucken wie viel verdiene ich das Ganze nicht darf halt nur so weit verringern dass ich an den 0 auf und nicht mehr das heißt ich darf ab März gewinnt und was man sich überlegen kann ist dass wenn sie diese wenn die sich ein wenig Paar eine optimale Lösung hat mit Y strich größer 0 das ist die selbst und auch immer Frick größer als 0 wählen darf um tatsächlich was zu erreichen aber was wird überlebt haben es einfach und was ich jetzt hier zugegebenermaßen etwas Formalin geschrieben hat ist das y 2 Strich er ist zulässig für D und wir transponiert y ist hatten echt kleineren Ziel Funktionswert also W transponiert y spricht ,komma das heißt ich hab nicht verbessert und jetzt kann ich die gleiche Runde noch einmal mach ich geh wieder in ein neues y setzte wieder das regierte Primaner Problem auch schon die wieder das duale an und macht das und damit hab ich jetzt also mein Problem lösen eine LP ersetzt durch lösen wir diese LP ist mit der man mit dem Vorteil dass dieser LP so hoffen wir zumindest einfacher wird und jetzt kommt auch so langsam wieder näher an das was im Skript steht wenn wir Cop und jetzt mal einen konkreten Fall an oder tatsächlich funktioniert und der schon Spezialfall alles von dem was wir nachher mit Approximation so Algorithmen machen denn was wir
uns anschauen ist wir schauen uns an erst mal so bisschen was passiert wenn ich das ganze Anwender auf das kürzeste Wege Problem also ein Beispiel kürzester Wege nach wir werden auch gleich schon Variante von dem Algorithmus brauchen aber die kommt die relativ natürlich raus ich will jetzt mal relativ merkwürdiger Art das LP aufzustellen die ist nicht empfohlen wenn man versucht das selber aufzustellen aber sie passt halt gerade so wunderbar in diesem Rahmen rein also das Primaner Problem wird so aussehen dass ich sage wenn ihre 10 transponiert x wobei x E ist eben entspricht jeder kann ich eh im Weg ja also die Variable sagt mir die kannte ihren Weg es diesen indiziert über mein Graph also seit April ist geh drauf Knoten Menge Frau kannten wer und ich sehe mir sozusagen für kannte er ist dem Weg für alle E aus seit ab jetzt Variablen die mir sagen ob die Kanten weg es und ich hab Kosten C sozusagen was in der Kanzel die und was ich jetzt mache ist die WM angekündigt etwas merkwürdige Formulierung ich sage für je da Partitionen Caro mehr machen wir ja doch V 1 und V 2 mäht 1 vereinigt V 2 =ist gleich meine kannten Menge V 1 geschnitten V 2 ist die leere Menge und er ist also es Start Knoten die Zielquoten und was ich fordere ist dass es in V 1 S und T NV 2 S stets über alle Knoten alle Partitionen gehen und sage die Summer fahren die aus Delta V 1 also alle Knoten die irgendwie rausgehen Hausfrau 1 die Summe die muss größer gleich 1 sein also Bild erst C Knoten 1 Knoten 2 Kosten da dran nehmen wir mal so und was sie jetzt machen das entspricht sondern Paarung v 1 v2 na ja ich suche mir so ne Menge V 1 er aber ich suche mir so ne Menge V 1 nehmen mal die sich hier Untermenge V 2 und betrachte alle kannten die von 1 nach V 2 GB das verbinden also einfach den Schnitt der Fans war einst fort von der Partition V 1 V 2 induziert wird also sich hier geht man kannte rüber und hier geht mehr kannte rüber von vereint war vor 2 und das ist mein steht welche induziert wird und was eine Bedingung sagt dass da ja jeder Weg der von der nach des führt der muss bitte über Wunsch mitgehen irgendwann muss ich da mal rüber und das gilt für alle Zerlegung in 2 Knoten so genannte Schnitt Formulierung für solche Wege Probleme das ist eine kürzeste Länge Problem tatsächlich sehr sehr unökonomisch also insbesondere am exponentiell viele Nebenbedingungen das macht uns zwar kein Problem weil wir die gezielt mit oder haben wissen es geht in Polynomialzeit aber es ist jetzt nicht wie soll ich sagen nicht die 1. empfohlene Variante wie man das formuliert aber für die Probleme die wir gleich kriegen die sogenannte war die Verallgemeinerung von dem Ding das sogenannte Meetings hat Probleme er ist das sozusagen die Formulierung der Wahl und dafür werden auch die Approximation es Algorithmen beweisen aber hier wird erst mal die Situation der sagen für jeden Schnitt egal wie ich V 1 und V 2 Wege solange es in der einen und den andern Menge ist irgendwann muss ich da mal rüber mit meinem Weg und unter allen diesen Dingen wieder einmal rüber müssen sich die minimalen Kosten und ich jetzt auch an in Zukunft das mein Kosten Vektor c das der größer 0 ist also ich will keine von mir aus kann noch größer gleich 0 1 aber ich nehme jetzt erst mal größer 0 an das heißt auf ein kann nicht nicht nur nicht negative sollen echt positive kosten das bedeutet Dennis insbesondere das dieses Ding hier auch zu dem Weg wirklich als Lösung kommt weil es sich nicht lohnt andere kannten einfach dazu zu nehmen sondern über kannten sein automatisch durch die Minimierung heraus oder selbst machen wenn ich die Tafel gewischt habe so zumindest in Teilen am es eben genau dieses Schema hier oben anzuwenden aus dieses Problem wenn ich wissen wenn Ihr Fragen habt bitte das jetzt der richtige Zeitpunkt ich mal ok ich lass die sein 1. Mai stehen damit wir gleich wissen wie wir vorgehen müssen 1 an diese etwas Merkwürdiges diese etwas merkwürdig formulierte LP jetzt kommt manchmal das duale dazu an also zieht dass unser duales na ja entgegen für jede Partition kriegen eine Variablen ich jetzt mal nur mit dem V ein 2. Frau als 2 ja offensichtlich dadurch ja schon bestimmt das ich also nur mit dem V 1 bezeichnen das heißt Sie kriegen Variablen in dem V 1
und wir kriegen für jede Kante aus E wegen eine das heißt wir maximieren wer 1 auf der rechten Seite die maximieren die Sommer V 1 Teilmenge V von den y V 1 die maximieren wir auf die Gefahr hin dass ich sie nie wieder sehen Orients jetzt gehen wir hin und kriegen für alle ihr aus E die Nebenbedingungen das die Sommer war dass die Summe der E die aus dem Delta V 1 kommen nein Frau 1 so das Ehe-Aus Delta V 1 zu 1 die Sonne darüber diesen Sommer soll gleich sollen kleiner nicht denn soll kleine gleich dem es ein seit jetzt hab ich hier nur ein exponentiell viele Variablen ok das kann man also alles das nicht lesen konnte weg oder noch andere Teile ok ich schwarz auf wieder hin also V 1 so dass das wie aus dem V 1 ist also ich so mehrere über alle die Knoten Thale so dass das Ei aus dem nur Schnitt von dem V 1 ist also genau über diese er ist was seit genau umgekehrt ist sachlich grob Mehr eine Kante an und jetzt geht mir alle Schnitte so dass diese kannte in dem Schnitt drin liegt und da so mir ich jetzt eben die Variablen die zu diesem y V 1 gehören und da wir überall nur Einheit nur Koeffizienten hat neben 0 oder 1 sind steht da eben dann genau dieses um ach so und das y es natürlich größer gleich 0 genauso wie hier das X groß vergleichen fahren dass unser duales Probleme und da wir angenommen haben dass das C immer größer 0 ist ist die Nulllösung alle ich auf 0 setzen ist zulässig ich hab Zufahrten zulässige Lösung für mein alles Problem weil 0 erfüllt diese Bedingung wenn ja alles muss steht hier 0 und das ist sicher kleiner gleich den Komponenten von dem 10 was passiert jetzt wenn ich die hier mit fragen dessen Variable das Emsland Vereins für eine solche Knoten Menge also deshalb die vereint sind einfach Teilmengen von Frau hier alle Teilmenge aus und kriegt dann ebenso so eine Variable für jede dieser Knoten man wie sieht es jetzt aus wenn ich mir das frisst wenn ich mich zu der konkreten gegebenen y das restringierter Free mal angeschaut ja das restringierten Triennale für mein Problem sieht doch so aus ich gucke mir mein ihren ich gucke alle 10 und nicht auf 0 gesetzt habe und sagte na ja für die y ist auf 0 gesetzt habe da möchte ich wenn auf y nicht auf 0 gesetzt hat da erlaube ich irgendwelche Werte für die x hier oben da muss das größer gleich sein für alle anderen Verlag ich dass spricht es und ich verlange jetzt eben das S und T gleich sicherheitshalber noch mal gucken wie es und wie es definiert nicht dass ich hier noch mal das es genau so also was ich gerne hätte ist es muss jetzt hier mein Problem aufsetzen und dann wenig wenn das y e gleich 0 das dann erlaube ich ihr komplette Freiheiten nehmen indem er ihr X wenn man das y ungleich und es dann verlang ich die will ich hier in diesem minimal diesen diesen leitet minimieren und das jetzt nach dem das überhaupt alles lösen zu können hat wir werden versuchen wir werden versuchen diese duale nur so werden jetzt versuchen das 1. Artikel das ist das der Rahmen in dem wir arbeiten wollen und was wir jetzt machen ist wir gehen jetzt schon gleich den Schritt über und überlegen uns wie wir das vereinfachen können indem wir sagen wenn ich das hier aufsetzen würde mit welchen Problemen das kann sich auflösen ich will ich mir zu sagen das Leben noch einfacher machen als es hier der Fall ist ich will dieses kürzester Wege Problem angucken und will das noch einfacher haben und um das noch einfacher zu haben ignoriere ich denn nur ein Flop in Gori ist jetzt erstmal sID Bier an der Stelle einfach mal den dualen schluckt und versuchen mir damit das Problem einfacher zu machen so und mein Vorschlag wäre da ist gerade sonst irgendwie den Eindruck habe hat verlässt sich nun dazu kommen nur 5 Minuten draus am 8. zu zu n doch ok er alle
wieder da der CDU jemand ok ok dann wenn ich die richtig deute mit ihren 5 Minuten sprechen dann sind die jetzt um am also wie sieht es aus wir haben wir können jetzt dieses Schema daraus an man das war was ich mir aufgeschrieben habe ist nur gerade aufgefallen ist wenn das gleiche Problem noch mal mit der leicht alle Methode der Primal dualen Variante machen das kollidiert irgendwie ich halte das nicht für sinnvoll wenn wir das jetzt zweimal mit unterschiedlich also leicht unterschiedlichen Varianten lösen da ich mir ein falsches Beispiel ausgesucht daher werden jetzt direkt an der Stelle schon Schnitt machen und sagen ohne Beispiel das ist die klassische Primal dualen Variant der das Thema ist ich versuche löse das Primal das ist regierte Primaner wenn die hier feststellen dass meine x Bestrafung wenn ich jetzt hier mit der Nulllösung fahren wenn ich feststelle dass mein nix Bestrafung sehr hoch ist wer überhaupt diese ganzen Bedingungen dass das größer gleich 1 wird muss ich DX hochfahren und das darf ich nicht als mit meinen y ist an der Schranke werden das ist im Wesentlichen was passiert und dann muss ich ja aus meinem restringierten Boualem Problem ableiten wie ich mein y hören wir verlassen aber jetzt genau diesen klassischen dicke könnte es also im Prinzip man kann es mit diesen Dingen einfach machen und lösen versprochen aber wir verlassen jetzt den klassischen Teil und gehen zudem etwas neueren Tal nämlich wie gehen dazu das wirklich als Approximation es Algorithmus zu benutzen das heißt wir wollen jetzt gar nicht mehr das LP wirklich lösen wir wollen's nur approximieren selbst der Probleme die Polin in Polynomialzeit lösbar sein dass das manchmal praktisch weil diese Primal Verfahren relativ gute Komplexität haben sie ihre Approximation Scythe und es daher sinnvoll sein kann 5 das zu nutzen statt dem exakten Polynomialzeit Algorithmus und dazu betrachten wir uns jetzt können wir entweder das kürzeste wegen Problem oder wir betrachten jetzt allgemeiner das sogenannte hitting Probleme und im Wesentlichen war diese Formulierung das kürzeste wegen Problemen genau so eine Formulierung des Settings ist also Meetings hat funktioniert im wesentlichen genauso wie wir gerade das 3. Mal wir gerade hier das prima das führen kürzeste Wege hatten wir und seine Grundmenge in Analogie zu dem was wir gerade beim kürzeste wegen Problemen an und dann wenn wir die mal E und wir betrachten mal wieder minimiere C transponiert Text n Sommer und jetzt kommen sogenannte in die Mengen die wir treffen müssen das heißt wir haben sie einen ich drehe wir heizen sich sicher groß ein P die kommen aus unserer Grundmenge und wir sagen wir müssen die treffen das heißt wir brauchen Element aus es dass in diesen Themen drin ist da das ist genau diese Bedingung und wir verlangen das X aus 0 1 6 und natürlich kann man jetzt eine LP Relax ierung bilden indem wir diesen Bedingungen hier mal ignorieren und ich x größer gleich 0 ersetzt außerdem gehen immer davon aus dass unser sie hier jetzt größer gleich 0 ist und was wir also brauchen wir wie würden wir haben Teilmengen und die müssen wir treffen deshalb Petting sagt wir müssen diese Teilmengen einfach treffen und die kürzesten Wege Formulierung von Leben war genauso Meetings hat Formulierung die hat dich treffen muss sind genau diese Schnitt diese Kantenlängen die Schnitt überbrücken und jede davon muss ich treffen das die Indicating Zeit Formulierung und das Duale was ich geleitet habe sie dann im Wesentlichen mit der andern Notation genauso aus wie das Problem was wir eben ab und für die die mitlesen jetzt sind ja auch wieder fallen in Skript an der Stelle uns bisher nicht auf Seite 104 105 das duale Problem hat leben auch stehen wir hatten gesagt das ist einfach maximiere die Sonne über Aldi y T wie das Weise kuckt mal indizieren anders sie machen einfach lassen jedes T weg und zum einfach über schon gleich 1 bis hin und wir kriegen das ist genau das was ich eben hatte wir kriegen eben nie so dass die Austria ist y e kleiner gleich CE und das für alle er aus und die y sind alle größer gleich und die Schutzbedingungen sind genau diese Stoffe Bedingungen die wir eben hatten das heißt wenn ich irgendwie eine Menge und die heißt im Skript jetzt habe also wir gehen mal von der PRI malt ferner drehen eine Lösung aus ist klar dass wenn mein B aus A ist also wenn
X E gerade größer als 0 ist na dann brauche ich eben und das ist
genau die eine Bedingung brauch ich eben dass ihr mit ihr NTI dass dieser über diese y is das die gerade zuerst das ich also hier teilte und genau so wenn y e größer 0 1 brauche ich und das ist jetzt auch wieder nur eine Spezialisierung der Schutzbedingungen vornehmen brauch ich das geschnitten mit dem die das das gleich 1 ist ja es einfach nur die beiden Schutzbedingungen nochmal und die Dinge selbst gar ähnlich vorzugehen wie eben nur Folgendes zu machen bisher hatten wir gesagt ich möchte gerne meine Primal um eine duale Lösung aufeinander zu führen in der Hoffnung ein LP zu lösen und dafür hab ich dieses ganze restringierten Primaner das duale davon ausgesetzt und versucht die aneinander anzunähern es geht jetzt nicht weil wir wollen ja gerne ganzzahlige Lösung haben und wir können nicht erwarten dass die ganzzahlige Lösung auch grade noch die Tilburg das die gerade die optimale Lösung das sonst können sich Hermann LP einfach lösen das vielleicht eleganter zu machen als einfach hier dieses diesen Rinaldo ein Ansatz zu machen also gehe ich hin und muss damit leben dass meine prima Lösung vermutlich nie so gut werden dass sie Wahl das ich hierzu zu dazu passende Spring also dass ich sitzen Primal ein paar ergänzen kann als muss meine duale Lösung hochtreiben und eine prima Lösung runter treiben muss aber damit leben dass ich jemanden Dualität zu bekriegen werde und sie Ideen dazu kriegen das Na ich ignoriere das mit dem dualen Flops wenige wie es einfach also ich behalte meinen Primal schon von den will ich auch immer als Wink aber den dualen Schlupf den vergessen war also das Herz nach wohl es ist wir gehen so ähnlich vor wie geben wir konstruieren uns unser restringiert prima unser zum Skript heißt es hier wir setzen unsere Menge an so das sind genau die Kanten so dass die Sommer über die Element TIA so blau die die ich treffe dass die gleich sie es wird also hier wir gucken uns an wo wenig aktiv und das ist genau diese Bedingungen her wenn an diese Menge hier also ich wähle praktisch nicht konstruieren eine prima Lösung fest ich sage na ja ich nehme genau diese wo ich hier wo ich hier fest in das ist das Gleiche was ich vorhin bei dem restringierten Freeman gemacht habe oder sich da sogar noch härter einfach jetzt da auch glasig hat 0 oder 1 zur Auswahl sagen kann er wenn nicht 0 sein soll dann muss es eben ein sein ich keine Wahl da hat sich die sondern wenn ich weiß mein X soll größer 0 sollen da ja da muss man x halt alles gewesen war also kann ich das hier so als länger schreiben Na ja wenn aber mein an unzulässig war also wenn das war nicht in das X das den für den Zweck du zudem als wenn das nicht diese Bedingungen erfüllt dann hab ich immer verletzten Bedingung das entspricht dem was ich in meinem restringierten Rivalen nicht negativen bleibt einfach kriege das eines dieser es wir vorhin hatten dass eines dieser ist eben größer als 0 wird weil ich halt hier nicht über diese 1 Komma und Na ja das heißt unzulässig infiziert doch es gibt eine Gefahr mit Tecra geschnitten an Gleis ihre Menge in einem TK trefflich halt net das die einzige Variante wenn wie prima es unzulässig wird ich treffe irgend so eine dieser Mengen halt nicht ok Sohn den und da sagen wir halt TK besser gesagt eigentlich die hierzu gehörende Nebenbedingung an es verletzt wer also hier hab ich ja für
alle die aus er 1 bis T Mehr Sonne Nebenbedingung gebaut und das ist hat die Karte davon verletzt und jetzt diese komische Konstruktion mit dem Mädchen und ihrer Folgen hatten wir haben vorher die Situation gehabt manche von diesen und sonst müssen wir verringern manche müssen wir erhöhen also wenn Eltern die Formulierung hatten hat mir 2 Schranken für das Epsilon die eine Schranke die verhindert dass unter 0 laufen und die andere Schranke die verhindert dass sie zu hoch laufen aus der Konstruktion die wir hier machen und weil wir den wahren Zweck vernachlässigen will ich hier nur ich einen einfach immer nur das Brust ich gar nicht drum kümmern denn was ich machen kann ist sage näher ich würde jetzt einfach mal y k solange er sich an die Schranke komme den offensichtlich soll ich muss ich ja hier noch was tun also ehrlich man y solange bis sich der Unterkante neue an die obere Schranke ,komma und das ist die kannte dich dann wohl dazu nehmen muss also ,komma werden bevor wir da an der Stelle weiter machen unser kürzesten Wege Problem ich hatte ja schon den Grafen gemalt wir hatten hier 2 2 1 5 es The wenn ich mir jetzt tatsächlich den Schnitt den ich vorhin ein gemalt hat einen Korken demnächst diese Schnitt und mir das mal ansehen also nehmen an Wärme y müssen 0 das heißt keiner kannte ich bisher drin gewesen bisher keiner kannte also y gleich 0 ist deren Länge neuer was ich will sich dieser öffnet das offensichtlich verletzt na dann ist der blaue Schnitt verletzt ja was Nachrichten mehr was wir vorhin gemacht haben war wir waren uns des letzten Lohn gesucht dass wir hochdrücken können also hier sagen wir na ja dort jetzt bitte dass selbst wenn man also das y solange hoch und wir nehmen eben ein ganz spezielles einen ganz speziellen Jungs weckt und der nicht nur den Herrn y k 1 1 stehen hat um 0 sonst das heißt wir können einfach sagen vor es wird dass man die Analogie zu zufrieden y 2 Strich kam auf das Minimum und das ist eben genau nur die eine Hälfte der Bedingung die wir vorhin hatten aber da wir nur erhöhen ist das kein kein Problem seit das auf das Minimum die minimale kannte fahren C -minus die Sommer hier ist nicht krank e Element TK so mit der y i also ich gucke mir an und y i für i ungleich K 1 und 2 ,komma setzt sich auf YT das heißt dass ich mach ich sicher höher einfach um den einen Einheitsvektor wo Car sozusagen der Eintrag ist der nicht auf 0 gesetzt wird und an mir die Bedingungen die wir vorhin hat nun wirklich erhöhen darf das hatte man die wird genau die sich hier was heißt das ich schaue mir alle kannten im Schnitt an was soll das denn noch kann die braucht Mehr ich Geld und super dann wir haben keine weitere Farbe erstmal Ossi gelb und blau was ich jetzt mache ist sich Cook Mehr an um wie viel kann ich dafür wenn einer dieser hier wird aktiv sobald ich das ist y k auf ein Viertel ja das ist was ich machen kann mehr darf ich nicht weil sonst der letztlich die Bedingung die ich hier bekomme sonst werd ich hier größer als das ich ok also nochmal und Gruß und das selbe steht hier oben auch noch mal das heißt das ich gemacht habe sich für größere jetzt meine Dual Variable und dann wird plötzlich die seine kantig aktiv das heißt wenn bei der nächsten Runde wenn man der nächsten Runde hab ich mir bekannte Mehr immer nix ich hab mal ne Menge in meinem besser gesagt sowie die Notation hier ist ich hab meine um 1 erhöht seit dem 2. Schritt von dem Algorithmus das ist passiert ich hab einfach eine kannte man den Grafen ich hab zum Teil die Moral Variablen und ein Update für die Moral Variablen gemacht das heißt ja schreiben uns der nochmal neu wählen wir haben jetzt 2 zu also wir haben diese kannte in dem
Grafen drinnen und hat den Wert ja zu sagen zu haben dass Y von dem 1. Schnitt wenn wir den Schnitt mal die einst dann dürfen wir hier überall 1 sagen aber dass das gerade mal das heißt wir haben hier das y 1 S 1 es kann man neben dran schreiben das heißt hier sozusagen die Verletzungen die schreibe ich mein Geld dran ja mir sozusagen 0 verletzt so hier haben wir noch eine Verletzung also um wie viel wir hier von MCI weg liegen also Geld ist immer C E -minus so Mehr die E 1 1 t die y hier haben wir nun hier haben wir eigentlich die haben wir 2 und ja immer noch so das heißt was wir gemacht haben ist werden wir die 1. bekannter eingebaut und dann tatsächlich angefangen sozusagen hier die Variablen zu abdecken Na ja was kommt jetzt es wenig mehr neuen Schnitt nehmen wir uns zum Beispiel mal diesen Schnitt was ich sehe ist nur ich kann hier wieder anfangen meine Ypsilons zu erhöhen das ist sozusagen T 2 und jetzt kann ich anfangen und am 2 zu erhöhen wie mache ich dass ich y 2 hier natürlich erstmal um allein den weiter kann ich nicht mehr kann ich hier meine Verletzung nicht erhöhen also weiter kann ich nicht um sozusagen die Verletzung Auszug seit setze auch y 2 auf 1 und kriege das bekannt neuen den Schnitt dazukommt ok das ist sozusagen die wir jetzt weiter vorgehen werden und der Reihe nach dadurch kann man diesen Grafen hinzufügen was ist der was ist und sollen jetzt was habe verallgemeinert gegen oder was eine vereinfacht das präzise gesagt dass eine vereinfacht gegenüber den klassischen Primal dualen Ansatz dadurch dass wir den wahren ignorieren kommen wir hier in der Situation wo wir immer nur auf müssen ja ich erinnert wir hatten vorhin ja eben sozusagen das die Ärzte nur muss entweder größer oder manche werden klein und da muss ich Ihnen dass das kleiner gleich 0 wird dadurch dass ich den wahren Zweck ignoriert Atlanta erstmalig in dieser konkreten Situation hat aber auf ich schrieb immer weiter kann raus und dann ich kriege ich kannten die wenn man sich mal den Ursprungs Grafen anguckt offensichtlich nicht den kürzesten Weg zu suchen haben denn das ist ne Sackgasse ich will diese kannte und eigentlich später gar nicht man kürzesten Weg haben alle die Standardversion ist erstmal nur die schieben und hoffen dass alles gut geht und auch wenn diese Variante jetzt als Endergebnis einfach liefern wir Distrikt danach einsichtig die beiden oberen kannten ist die dafür was gut denn und das ist jetzt sozusagen die 1. Teil wo wir noch was beweisen für manche total einfachen wurde nächsten nicht sind nicht total einfach als Emanze gutmütige sagen wir es mal so für Mainz die gutmütige Probleme es das schon gute Approximation es Algorithmus obwohl ich offensichtlich da irgendwie und kannten noch mit drin lassen also schreiben jetzt erst einmal diesen Skript steht die Grundversion für diesen Algorithmus die schreib ich nochmal an und dann diskutieren wir im Wesentlichen was sozusagen noch die zusätzlich Bausteine sind die dafür sorgen dass man schon mal das als ein Approximation es Algorithmus Inc das wird dann vermutlich für heute auch schauen wir mal vielleicht kommen wir noch zu den sagen so weit noch mal also die Grundversion ist es Hagen an Gesetzen y gleich 0 in unserer Formulierung und entsprechend das kommt ja dann automatisch raus setzen unser an auf die leere Menge das war der Anfang nicht gerade gemacht hat ob und dann kriege ich Schleifer solange es gibt da so ein K gibt so das Tecra Element a die leere Menge ist Fähigkeiten er mit Kleinkram ein wir aus ihnen gibt so dass eben y so dass die hier können I so dass die Summe der Zulagen wieder dran sind gleich CIS also der sich mit dem einen an die obere an die an die Schranke komme und wenn dem so ist Na ja das ist meine Art und das erhöhen so unerquicklich noch sozusagen hier das Ende von dieser Schleife und das nächste ist wir sind fertig ist das hat seinen Grund Version von dem ganzen den und das hat eben versucht an diesem Beispiel einmal durchzuspielen ist fangen von y 0 an China die Ärzte die entsprechenden Schnitt Werte so lange hoch bis ich eben tatsächlich an bist sozusagen merke dass ich neues ihnen zufügen kann und das macht macht wir müssen also dadurch dass ich jetzt allgemeine wenn Meetings hat geredet habe und irgendwie das alles lässt den einen das nicht so richtig greifbar ist wir müssen auch mal nach Annahme machen darüber was das Jahr angeht wie man hat uns gesagt dass diese TKV die wir kriegen irgendwie in denen der komischen Relation zueinander steht oder nicht denn in der Relation zueinander stehen es könnte sein dass die alle schön enthalten sein Sohn aufsteigende Kette bilden oder sonst wie wild nichttrivialen steht miteinander haben wir gehen ab sofort den man das nicht und TK Krieger das sich einige Inklusion minimale Menge bekommen habe das ist beim kürzesten wegen Problemen kann kein Ding weil die sind alle nicht ineinander enthalten aber es gibt hätte ich hat Probleme wo man weiß die sind alle in einander enthalten oder zumindest substanzielle Teile sind im Namen enthalten wenn ich ab sofort immer an ich kriege eine minimal verletzende Menge das heißt wie kann ich herausfinden wie gut meine Lösung von diesen Dingen war Na ja wie sieht das aus was ich jetzt mache es 2 aber das Ergebnis
das Algorithmus gut oder gerade weil die die Nummer 1 das ist also Säckel 13 Na ja was kann ich denn machen ich gerne etwas sagen wir was ich aber sehr zäh transponiert Ex das heißt das ist die Summe aller er aus ehe so das als hat die Summe über alle ihr aus aber sie eh wenn es 1 aber dann kriege ich dieses Summer was ich jetzt mache ich weiß ja dass ich meine y so weit erhöht habe das für alle er aus galt dieser über die Ypsilons bedauern würden die sind gerade CE das heißt ich kann diese c't ersetzen durch die Sommer ja das ist alle die so dass ihr aus Austria ist und darüber die y ist dann genauso war definiert ich hab die Erbsen und so lange erhöht bis ich Gleichheit bekommen hat und nur die mit die mit gleicher 3 eingenommen hat die kam in meine Arbeit das heißt ich hab das Mehr gut und dann kann ich einfach mal viel Spaß erlauben und die Summation vertauscht und was sie nicht mehr was ich sehe wenn ich mir diese Bedingungen hier mal angucke das ist einfach genauer also dass ich im y hier rein nehmen da passiert doch nur wenn man es wenn der Schnitt von dem an mit dem T genau 1 das heißt ich darf hier sozusagen diese diese Bedingungen die hier steht dieses Element Idee kann ich doch ersetzen ich sagen na ja das ist doch eh gleich 1 bis B und dieser ersetzt das durch tägli geschnitten geschnitten a mal y die damit wir diese Bedingungen die hier drin steht der sozusagen ich hier hier rein gezaubert das heißt ich hab schon eine Abschätzung der für wenig insbesondere wie viele die Abschätzung hängt davon ab wie viel hab ich viel zu viel gemacht ich gehe also wo ein Problem bei diesen Beispiel das ich hatte mich ich zumindest in Teilen vielleicht überzeugt hat so wir 3 Ausgaben hätte das als Lösung liefern aber der Reihe nach kommen diese 2 zweier kann die oben Sonde rein und die 1 und zum vakante kommen hier rein oder hier weiter auf alle jetzt endgültig malen Weg gefunden hat was das aber heißt das doch dass dieser Schnitt hier der Blaue dieser Blau Schnee Tiere der sozusagen über gesättigt da sind mehr drin als ich eigentlich haben wollte da er sich kritische plötzlich in diesem Schnitt mehr kann als ich eigentlich formal brauche das heißt dieses Ding hier wird größer als er einst sein eigentlich soll hier nur 1 stehen bitte aber da passiert es mir dass ich einfach mehr könnten reingenommen hat und daher sozusagen größeres den kriegen aber wir haben ab und an mal den Fall wo das wir jetzt wenn wir versuchen Approximation Scythe abzuschätzen dass wir dieses Ding tatsächlich beschränken können also weniger haben das die geschnitten kleiner gleich ein für alles ok ist es jetzt her hier für alle die mit y größer 0 wenn ich dieser Abschätzung hat dann hat es das derzeit Approximation es Algorithmus bei das hier ist die optimale Lösung und Mehr als alte aber wenig ich ja kriechen Faktor alter Wein also ich Krieg ja wenn man das mal formal auf schreibt das c't iX ist krank kleine ist ja gleich wie das gerade hatten die Summe über die I I geschnittene mal y nie und wenn das Geld Na dann ist das doch kleiner gleicht so mit dir Zählern I und das hier ist offensichtlich nur unsere Schrank es offensichtlich der Schranke für unser Problem bei der genau deine Situation war dass sie jedes an diesen Sites dass sie treffen müssen auch nur einmal getroffen habe da wir wissen dass das von den y kommt und das von der globalen LP Lösung haben wir dann die Approximation sehr Goethes also weiter und das war es relativ zentrales was wir was da das Argument dass meine wird enorm sind Dual zulässig das heißt sie sind nur untere Schranke für den optimalen Wert so eine untere Schranke für den optimal wird meine LP Lösung besser als das kann ich sicher nicht werden nur war daher das duale Problem so konstruiert dass die Summe der y die genau diese Zielfunktion da war bei die rechten Seite überall 1 machen das heißt wenn ich dieses Ding die mit Eifer beschränken kann dann kann ich automatischer nicht automatisch diese Approximation hier das heißt was ich brauche ist eine Schranke unabhängig von allen für die diesen Fall beschränkt dann hab ich in Haifa Approximation es Algorithmus so schlechte Nachricht für die meisten Probleme mit funktioniert das und dann wenn ich kein solches als es gibt aber auch gute Nachrichten für manche findigsten schönes Alfa zum Beispiel ich das kann nur Deckungs Problemen gilt das T E immer gleich 2 ist für alle das Gold der der Problem es genau so formuliert dass es darum geht finde genügen Knoten dass sich alle kannten dem Grafen sind irgendwie einmal treffe das ist meine Grundmenge sind alle Knoten und will so Zhang mit den Knoten versuchen alle Kanten zu überdecken da jede kann das aber nur 2 Elemente es wird 2 Knoten die man überhaupt haben darf also gar nicht die The East alle 2 das heißt insbesondere das ist auch immer 2 das heißt schon diese Standardvariante 1. 2 Approximation zu Algorithmus für das Cloud über Deckungs Problem Stormarnplatzes kürzeste Dinge Problem ist das aber nicht der Fall weil diese schnellte die darum auftreten können beliebig komische kann kann Liebe Gruesse kriegen ich überlege waren kürzt wegen Problem es kann ja sein dass man Startknoten S irgendwie beliebig viele kannten hatte daraus danke ich diese Abschätzung schon gar nicht mehr machen und das heißt ich muss mir etwas schlaueres überlegen um hier Na Abschätzung zu kriegen und im Wesentlichen aber das was man sich jetzt schlaueres überlegen muss auch schon gesehen unser Problem was bei so Abschätzung halt auftreten kann es was wir zusätzliche Karten kriegen kann jeder gar nicht wollen und jeder 4. ja lassen nie einfach Ideen und deutschen Anwendern paar kannten aus gründeten die ja nicht ganz so offensichtlich sind wir wir sie gerne hätten aber dann es ist sinnvoll die kannten wir gehen jetzt durch Umfragen ja wenn ich die Kanten nicht brauche ich kann sehr testweise rausnehmen und gucken ob ich noch zulässig bin kann jetzt gut da ich habe diesen Teil jetzt guck ich ich bin so bekannte raus bin ich noch zulässig und wenn ja dann kann ich ja offensichtlich weglassen so ist das Problem ja gerade konstruiert und im Wesentlichen 11 die beste Strategie und man kann sich auch überlegen warum aber wir werde wird weiß irgendwie mit raus ,komma wer gute Strategie ist das wieder eine rückwärts rückwärts zu machen gegenüber dem wie man eingesetzt hat also ich fange mit der letzten kannte die
man gerade eingesetzt hat fangen wir wieder an um zu testen ob ich nicht doch wieder draußen im Dorf also weiter ob wir uns selbst also diese Bemerkung hier es dann übrigens Satz 6 14 oder so aber es ist im Wesentlichen neben die Bemerkung Ende der das eben das Problem einfach genau so gestrickt ist dass es so gute Approximation es hat alle männlichen nahm wird wieder den gleichen Algorithmus wie eben als wir kriegen sozusagen 6. 15 als Algorithmus aus wie liefert jetzt nicht normal also ich hier ist praktisch immer Algorithmus 6 13 und danach im 1. also Pryce mehr schreiben ist also er steht im Skript aber ich schreib einfach die unsere Schleife noch mal hin also vor die dort gleich L zu allem wobei L die Zahl der Elemente aus Ahlen ist sozusagen verheilt ist aber ohne E J zulässig setzen wir ist ohne und also wirklich ganz wie gehen ein sehen wird und die Kanten an und sagen das war in Ordnung also können wir sehr also zum wievielten Mal auch immer das Beispiel ja und wir hatten ja die hat mir zuletzt eingesetzt im aber unzulässig zu sein sonst aber keinen Weg die hatten vor eingesetzt wenn ich die rausnehme braucht auch ein Weg also brauch ich auch Umweg zu haben wenn ich die rausnehme hab ich immer noch im Weg also kann ich die reichen und das ist sozusagen jetzt die verbesserte Variante dieses Primal Wahl Algorithmus ich habe einfach nur mal ein paar Elemente gestrichen was wir jetzt haben wir nicht also das wenn man auch oft rückwärts läuft so habe ich halt rückwärts alles läuft haben und jetzt komme noch ein Übel und wenn wir die haben können wir mit verbesserter Approximation 2 Eigenschaft zeigen insbesondere können wir zeigen dass der Algorithmus schon das kürzeste Wege Problem exakt zu viel ist dieser relativ einfach Algorithmus also die Definition die ich noch brauche ist die einer minimalen Erweiterung ein .punkt mobil hallo also Teilmenge E l ist unzulässig wo dann heißt es minimal Erweiterung ich mehr falls nur in den ebenfalls können wie eine Biene Maja RWE soll zulässig sein B er soll da drin enthalten sollen und na ja jetzt kommt die eigentliche minimal lität Eigenschaft wenn ich irgendwie raus Lt wer ohne dieses E unzulässig ok also es ist einfach es hat ein paar Elemente der zugeworfen und wenn ich das gemacht habe
nicht zulässig und wenn das die minimale wenn es keine Menge man B enthalten gibt die aber auch noch enthält unzulässig ist dann war das minimale hinter her erweitern so und das Herz wird in den verbleibenden 5 Minuten oder so um die nächste Approximation Scythe nicht damit die Konstante dann Beta heißen zu bereisen denn das heißt das dass ich jetzt in meiner was heißt dass ich irgendwas in dieser rückwärts Löschung nicht löschen kann wann muss erhalten bleiben Na ja wenn es wenn ich das nicht löschen kann dann ist doch klar das durch das sagen dann ist klar das ist unsere minimal Erweiterung drin gesteckt haben muss ja das reicht wir wissen das aber unzulässig das BE wurden Georg drin war das war zulässig und ich durfte das er hat nicht ja schon er das Tal der sie glaubt nicht lasch das heißt ich weiß auf jeden Fall das schöne minimal Augmentierungen geben muss wo das halt drin steckt das heißt es muss irgendwie so B geben wo der es drin habe also selbst sei aber aber es ist er 1 bis er ob wieder auf 1 und das ist unzulässig buchen denn sonst hätte ich ja dass sie auch drin lassen dürfen das heißt es gibt eine minimale Erweiterung werden es gibt eine B das hat diese neuen Elemente und enthält aber so dass das Ei in diesem Ding drin sein muss also das heißt er Ort muss in dem AF gewesen sein sollte dies dürften das heißt aber auch das heißt aber auch das ist das am geschnitten wie war das The immer kleiner gleich ist ist und dem was ich in dem P geschnitten mit dem T hatte ja es kann sein dass ich wenn ich elementare das ist sozusagen hier in dieser Erweiterung drin hat kann das brauchte ich tatsächlich um hier Zulässigkeit zu kriegen das heißt ich kann Ihnen Element es kann zwar noch ist also Element in dem B geben die ich nicht brauche aber irgendwas davon dich hier drin haben sonst sonst kann ich tatsächlich nicht der TI erfüllt also noch mal wenn nicht zum Tee Betrachter und sage ja das muss ich ja irgendwie erfüllt haben und das muss ich jetzt darf ich ja nicht verletzt habe und QC der meine minimale Erweiterung an dann ist klar das muss irgendwie nichttrivialen Schnitt haben mit den is zumindest mit einem der tief muss das trivial Schnitt haben weil sonst wär das Ding hier zulässig gewesen dann ist es aber so dass wir hier die richtigen ist ja genau das was mir die Zulässigkeit sichert das heißt es muss ein Tee-Ei geben wo tatsächlich ist notwendig war zu erweitern wenn es nicht notwendig war zu erweitern dann will ich hier ja zulässig gewesen und die Idee ist nun und das ist dann auch sozusagen die wie ich schätze jetzt dieses Jahr in dem ich sage wer kommt uns doch alle minimal Erweiterung seit ich kriege eine Beta und das ist das Maximum über alle minimal Erweiterung erst mal das Maximum über unzulässigen Mengen machen wir so rum also überall unzulässigen Mengen und dann noch mal das Maximum und das ist jetzt da alle B die Bar enthalten und wer seine
minimale Erweiterung und da war ist eben daran das ganze zunehmend über weggeschnitten Theater und A es die gewählte verletzte länger das ist etwas unhandlich also die Idee ich weiß ja was der Algorithmus tun wird wenn er feststellt als unzulässig dann während der mir eine Menge diese Menge nämlich TV von da guck ich mir an was ist denn die kleinste da die unzulässig da muss ich irgendwie erweitern damit ich zulässig werde was ist die kleinste Menge B mit der ich noch zusätzlich werden kann wird ganz schlecht und dann kann es sein dass sich viele Elemente brauche um noch zulässig zu werden es kann aber auch gut sein und ich brauche nur sehr wenig Elemente unzulässig zu werden und über alles nämlich das Maximum und das wenig später auf UND DDR gegeben so wie wir das konstruiert haben und so wie wir uns überlegt haben wie die Zielfunktion aussieht ist dieser Algorithmus mir Führung will weiter Approximation es Algorithmus für Ethik Zeit das heißt dass gemacht haben das Beta genau so konstruiert dass wir hier wissen das ist ein Beta Approximation zu Algorithmus für hätte gesagt und was dann Anfang nächsten Mal wird es zu sagen na ja wir können uns überlegen für das kürzeste wegen Problem das Beta 1 ist das genau hier immer wenn ich ein unzulässiges habe und sich in die minimale Erweiterung das dann immer der steht da gerade 1 wird und das sich also nur eine Kante brauche um sozusagen einen verletzten Schnittgut zu machen und das machen wir beim nächsten Mal und da kommen dann auch noch zu einer verbesserten Variante der Approximation sei wird man unsinnigerweise die konstante dank Ammar heißen
Einfach zusammenhängender Raum
Variable
Große Vereinheitlichung
Vektorrechnung
Menge
Reihe
Abschätzung
Vorlesung/Konferenz
Optimum
Sorte <Logik>
Vektor
Computeranimation
Geschwindigkeit
Extrempunkt
Rundung
Minimum
Reihe
Zielfunktion
Optimum
Computeranimation
Einfach zusammenhängender Raum
Nebenbedingung
Länge
Matching <Graphentheorie>
Graph
Minimierung
Zerlegung <Mathematik>
Kante
Vektor
Partitionsfunktion
Teilmenge
Summe
Variable
Menge
Fächer <Mathematik>
Koeffizient
Verallgemeinerung
Vorlesung/Konferenz
Schnitt <Mathematik>
Teilmenge
Menge
Vorlesung/Konferenz
Dualitätstheorie
Schnitt <Mathematik>
Computeranimation
Nebenbedingung
Menge
Vorlesung/Konferenz
Kante
Dualität
Ganzzahlige Lösung
Nebenbedingung
Folge <Mathematik>
Länge
Obere Schranke
Reihe
Gesetz <Physik>
Summe
Variable
Menge
Kettenregel
Rundung
Minimum
Vorlesung/Konferenz
Dualitätstheorie
Schnitt <Mathematik>
Inklusion <Mathematik>
Schranke <Mathematik>
Faktorisierung
Untere Schranke
Erweiterung
Punkt
Reihe
Kante
Zahl
Teilmenge
Summe
Abschätzung
Vorlesung/Konferenz
Zielfunktion
Schnitt <Mathematik>
Streuungsdiagramm
Konstante
Erweiterung
Menge
Betafunktion
Maximum
Vorlesung/Konferenz
Zielfunktion
Kante
Schnitt <Mathematik>
Computeranimation

Metadaten

Formale Metadaten

Titel Primal-Dual-Approximationsalgorithmen I
Serientitel Diskrete Optimierung (Optimierung II)
Teil 23
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/31791
Herausgeber Technische Universität Darmstadt
Erscheinungsjahr 2009
Sprache Deutsch

Inhaltliche Metadaten

Fachgebiet Mathematik

Ähnliche Filme

Loading...