[Effiziente Algorithmen] Überblick über den Stoff, SS 08

Vorlesungen, Seminare und Praktika aus dem Bereich Theoretische Informatik (Abkürzungen)
Lectures, seminars and labs from the area Theoretical Foundations (Abbreviations)

[Effiziente Algorithmen] Überblick über den Stoff, SS 08

Beitragvon Coolcat » 21.07.08 15:58

Code: Alles auswählen
=========================================================================================
Effiziente Algorithmen  - Überblick, SS 08
Prof. Dr. Berthold Vöcking
=========================================================================================

Dies soll keine Zusammenfassung sein, sondern nur ein kleiner Überblick über den Stoff.
Als Quelle dient das offzielle Skript der Vorlesung.

=========================================================================================
Kap.1 Flussalgorithmen
=========================================================================================
Netzwerke und Flusse
   Flussnetzwerk, Quelle, Senke
   Fluss
      Flusserhaltung, Kapazitätsbeschränkung, Wert des Flusses
   Problem: Maximaler Fluss
   Algo: Ford-Fulkerson
   Restnetzwerk, flussvergrößernder Weg
Max-Flow = Min-Cut
   Schnitt (Cut)
   Lemma: Max-Flow <= Min-Cut
   Satz: Max-Flow = Min-Cut
   Satz: Korrektheit von Ford-Fulkerson
   Korollar: Ganzzahligkeit
Laufzeit von Ford-Fulkerson
   Satz: Die Laufzeit von Ford-Fulkerson mit Breitensuche ist O(m^2 n) = O(n^5).
      Lemma
      Hinzufügen von neuen Kanten
      Entfernen von Flaschenhalskanten
Algorithmus von Dinitz
   Niveaunetzwerk
   saturiert, Sperrfluss
   Algo: Dinitz
   Korrektheit: klar
   Laufzeit
      Lemma
      Propagationsphase                                                        ̈
      Potential einer Kante
      Potential eines Knotens
      Forward-Propagation
         Überschuss
      Backward Propagation
      Algo: Forward-Propagation
      Beobachtung
      Lemma
      Satz: Laufzeit von Dinitz ist O(n^3)
Das Min-Cost-Flow-Problem
   Problem: Min-Cost-Flow
      Kostenfunktion
   Kosten eines Flusses, kostenminimaler Fluss
Der Cycle-Canceling-Algorithmus
   Zirkulation, Kreisfluss, negative Kosten eines Kreises
   Algo: Cycle-Canceling-Algorithmus
   Korrektheit des Cycle-Canceling-Algorithmus
      Lemma
      Satz
Der Min-Mean-Cycle-Canceling-Algorithmus
   Algo: Min-Mean-Cycle-Canceling-Algorithmus
   Laufzeit
      Min-Mean-Cycle, Phase
      Anzahl der Phasen
      Anzahl der Iterationen je Phase
      Lemma
      Laufzeit pro Iteration
      Lemma
      Gesamtlaufzeit
      Satz
      Satz

=========================================================================================
Kap.2 Algorithmen zur Berechnung von Matchings
=========================================================================================   
Einleitung
   Definition: Matching, maximales Matching, maximum Matching
   Problem: Matchingproblem
   Problem: bipartites Matchingproblem
   Satz: Laufzeit O(m sqrt(n)) für das Matchingproblem auf allgemeinen Graphen.
      (ohne Beweis)
   Varianten
      Gewichtetes maximum Matching
      Min-Cost Matching
   Gewichtetes maximum Matching <=> Min-Cost Matching
   Satz: Es gibt einen O(n^3)-Algorithmus für das gewichtete Matchingproblem auf
        allgemeinen Graphen.
      (ohne Beweis)
Bipartite Matchings und maximale Flüsse
   Satz: Das bipartite (gewichtete) Matchingproblem kann in Polynomialzeit auf das
         ganzzahlige (Min-Cost) Max-Flow-Problem reduziert werden.
Verbessernde Pfade
   freie Knoten, M-alternierend, M-verbessernd
   Beobachtung
   Lemma
   Korollar
Ein einfacher Algorithmus
   Algo: Maximum-Matching-1
   Satz: Algorithmus Maximum-Matching-1 löst das bipartite Matchingproblem in Zeit O(nm).
Kürzeste verbessernde Pfade
   kürzester M-verbessernder Pfad
   Lemma 9  (Beweis nicht prüfungsrelevant)
   Lemma 10 (Beweis nicht prüfungsrelevant)
Der Algorithmus von Hopcroft und Karp
   Algo: Maximum-Matching-2
   Lemma
   Lemma
   Satz: Algorithmus Maximum-Matching-2 hat Laufzeit O(m sqrt(n)).

=========================================================================================
Kap.3 Stabile Paarungen
=========================================================================================
Motivation
Definition
   Stabile Paarung
   unzufriedenes Paar
Lokale Suche
   Algo: Lokale Suche
Der Algorithmus von Gale und Shapley
   Algo: Gale und Shapley
   Satz: Der Algorithmus von Gale und Shapley terminiert nach maximal n^2 Anfragen mit
         einer stabilen Paarung.
      Laufzeit
      Korrektheit
      Bemerkungen

=========================================================================================
Kap.4 Einführung in die Lineare Programmierung
=========================================================================================
LPs in verschiedenen Normalformen (Quelle: Folien)
   Die kanonische Form
      Zielfunktion, Nebenbedingungen, Nicht-Negativitätsbedingungen.
      LP in kanonischer Form
      Beispiel: Flussproblem
      Beispiel: Relaxiertes Rucksackproblem
      Geometrische Interpretation
      Konvexität des Lösungsraums
      Behauptung 1.1
      Behauptung 1.2 (Lokales Optimum = Globales Optimum)
      Facetten, Faces, Kanten, Knoten
      Optimaler Knoten
      Beobachtung 1.3
      Geometrische Beschreibung des Simplexverfahrens
   Die algebraische Gleichungsform
      LP in algebraischer Gleichungsform
      Transformation von der kanonischen in die Gleichungsform
      Beziehung zwischen Hyperebenen und Variablen
      Basislösungen
         zulässige Basislösung
      Querbezug zur kanonischen Form
      Vereinfachte Darstellung von Basislösungen
      Beispiel: Tableaudarstellung von Basislösungen
Der Simplexalgorithmus (Quelle: Folien)
   Beschreibung des Algorithmus                                 ̈
      Der Simplexalgorithmus im Uberblick
      Pivotschritt
      Wann ist eine Basislösung optimal?
         Vektor der reduzierten Kosten
         Satz: Optimalitätskriterium
      Durchführung des Pivotschritts
   Beispielrechnung im Tableau
      Beispiel
   Berechnung der initialen Basislösung
      Der 2-Phasen Simplexalgorithmus
      "HilfsLP"
   Degenerierte LPs
      Kreise bei degenerierten LPs
      Verhinderung von Kreisen
         Blands Pivotregel
   Laufzeit des Simplexalgorithmus
      Polyhedron mit exponentiell langem Hamiltonpfad
         Hypercube-LP
      Der Klee-Minty-Cube
         Satz
      Weitere Bemerkungen zur Laufzeit
Die Ellipsoidmethode (Quelle: Folien)
   Vorbemerkungen
      Lemma A
      Lemma B
   Aufgabenstellung beim Zulässigkeitstest
   Die Ellipsoidmethode – Ergebnis
      Satz: Die Ellipsoidmethode löst den Zulässigkeitstest in polynomieller Zeit.
      Satz: Lineare Programme können in polynomieller Zeit gelöst werden.
   Die Ellipsoidmethode – Idee
   Exkurs – Ellipsoide
      Ellipsoid
   Die Ellipsoid Methode – High Level Beschreibung
   Verkleinerung der Ellipse
   Die Ellipsoid Methode – Laufzeitanalyse
Zusammenfassung (Quelle: Folien)
Dualität (Quelle: Skript)
   Primale und duale LPs
      primales LP
      Definition: duales LP
      Satz: Das duale LP des dualen LPs ist das primale LP.
      Satz: Schwaches Dualitätsprinzip
   Das starke Dualitätsprinzip
      Satz: Starkes Dualitätsprinzip
      Beobachtungen
   Zwei prominente Beispiele
      alternatives LP für das Problem des maximalen Flusses
      relaxiertes Maximum-Matching-Problem

=========================================================================================
Kap. 5 Einfühhrung in Approximationsalgorithmen
=========================================================================================
Einleitung
   Konstante Approximationsfaktoren
   Eine 2-Approximation für das Vertex-Cover-Problem
      Problem: Vertex Cover
      Algo: Approx-Vertex-Cover
      Satz: Approx-Vertex-Cover berechnet eine 2-Approximation des optimalen Vertex Covers.

   Approximationsfaktor als Funktion
   Eine logarithmische Approximation für das Set-Cover-Problem
      Problem: Set Cover
      Anwendungsbeispiel
      (Problem: Hitting-Set-Problem)
      Algo: Greedy-Set-Cover
      Lemma
      Satz: Greedy-Set-Cover hat einen Approximationsfaktor von höchstens H_n.
Optimierungsprobleme auf Graphen und Metriken
   Approximierbarkeit von TSP
      Problem: Traveling Salesperson Problem (TSP)
      Satz: TSP hat keinen Polynomialzeit-Algorithmus mit Approximationsfaktor alpha(n)
   Christofides Algorithmus für Metrisches TSP
      Definition: Metrik
      Problem: metrisches TSP
      Algo: Metric-TSP-via-MST
      Satz: Metric-TSP-via-MST berechnet eine 2-Approximation für das metrische TSP.
      Algo: Algorithmus von Cristofides
      Lemma
      Lemma
      Satz: Der Algorithmus von Christofides berechnet eine 3/2-Approximation für das
            metrische TSP.
   Approximation des Steinerbaumproblems
      Problem: Steinerbaum
      Algo: Approx-Steiner
      Satz: Approx-Steiner berechnet eine 2-Approximation für das Steinerbaumproblem.
Makespan-Scheduling auf identischen Maschinen
   Problem: Makespan Scheduling auf identischen Maschinen
   Analyse von zwei einfachen Heuristiken
      Algo: Least-Loaded (LL)
      Satz: LL garantiert eine (2-1/m)-Approximation.
      Algo: Longest-Processing-Time (LPT)
      Satz: LPT garantiert eine 4/3-Approximation.
   Ein polynomielles Approximationsschema
      PTAS fur Makespan-Scheduling
      Lemma
      Lemma
      Problem: Bin Packing mit eingeschränkten Gewichten
      Lemma
      Satz: Es gibt ein PTAS für das Makespan-Scheduling-Problem auf identischen Maschinen.
Makespan-Scheduling auf allgemeinen Maschinen
   verschiedene Varianten des Makespan-Scheduling-Problems
   ILP-Formulierung des allgemeinen Schedulingproblems
   Alternative ILP-Formulierung
   Überblick über den Algorithmus
   Lemma
   Der Allokationsgraph
   Lemma
   Lemma
   LP-Rundung mit Hilfe des Allokationsgraphen
   Lemma
   Satz: Das Makespan-Scheduling-Problem für allgemeine Maschinen hat einen
         Polynomialzeitalgorithmus mit Approximationsfaktor 2.

=========================================================================================
Kap.6 Einführung in Online-Algorithmen
=========================================================================================
Einleitung
   Online-Algorithmus, Competitive-Faktor
Das File-Allocation-Problem (FAP)
   Service- und Migrationskosten
   Obere Schranke für FAP
      Algo: (unbenannt)
      Satz: Der Algorithmus ist 3-competitive
   Untere Schranke für FAP
      Satz: Es gibt keinen deterministischen Online-Algorithmus mit Competitive-Faktor
            besser als 3 für uniformes FAP auf zwei Knoten.
Das Paging-Problem
   Seite, Seitenfehler
   Beispiele: LRU, LFU, FIFO, LIFO, RANDOM, FWF, LFD
   Marking-Algorithmen
      k-Phasen
      Satz: LRU und FWF sind Marking-Algorithmen.
      Satz: Jeder Marking-Algorithmus ist k-competitive.
      Korollar: LRU und FWF sind k-kompetitive.
   Nicht-competitive Algorithmen
      Satz: LFU ist nicht competitive.
   Untere Schranke für deterministische Algorithmen
      Satz: Es gibt keinen deterministischen Online-Algorithmus für das Paging-Problem
            mit competitive-Faktor besser als k.
   Competitive Analyse für randomisierte Algorithmen
      "oblivious"
   Ein randomisierter Marking-Algorithmus
      Algo: MARK
      Satz: MARK ist (2H_k)-competitive.
         Lemma
         Lemma
Beweismethode: Potentialfunktion
   Potentialfunktion
   asymmetrisches Competitive-Modell
   Satz: RANDOM ist (2,2)-competitive.

=========================================================================================
Kap.7 Ausgewählte Randomisierte Algorithmen
=========================================================================================
Lineare Programme in linearer Zeit
   Problembeschreibung
      "virtuell perturbiert"
   Algo: SeideLP
   Korrektheit
   Laufzeitanalyse
      Lemma
      Lemma
      Satz: SeideLP löst ein zulässiges d-dimensionales LP mit m Nebenbedingungen in
            erwarteter Zeit O(md!).
Randomisierte Suche nach dem Min-Cut
   Multigraph, Schnitt, Min-Cut
   Die Kontraktion von Kanten
      Kontraktion
   Algo: Contract(G)
   Exkursion: Unabhängigkeit von Zufallsereignissen
      unabhängig, bedingte W'keit
   Satz
      Lemma
   W'keitsamplifikation
   Algo: Fastcut(G)
   Satz: Fastcut hat Laufzeit O(n^2 log n).
   Satz: Fastcut berechnet einen Min-Cut mit W'keit Omega(1 / log n).
Monte Carlo vs. Las Vegas
   Las-Vegas-Algorithmen
   Monte-Carlo-Algorithmen
   Exkursion: Markov-Ungleichung
      Lemma
      Satz
      Satz
My software never has bugs. It just develops random features.
Benutzeravatar
Coolcat
Promoter
 
Beiträge: 2574
Registriert: 28.11.05 21:26
Wohnort: Kohlscheid / Düsseldorf
Studiengang: Informatik (Dipl.)
Studiert seit: fertig
Anwendungsfach: BWL

Beitragvon philipp » 21.07.08 22:09

Hi,
ich stelle beim Durcharbeiten des Skripts und der Mitschriften einen Katalog von mir wichtig oder interessant erscheinenden Fragen und Antworten zusammen.

Eigentlich habe ich die in einem anderen (nicht oeffentlichen Forum) gepostet. Aber ich dachte mir ich poste sie jetzt auch mal hier. Ist noch nicht ganz fertig, da noch Rest zu Approxalgos und Online-Algos fehlt. Kann sich ja trotzdem jeder mal anschauen.

Bitte jetzt nicht tausend kommentare, nur bei definitven fehlern bescheid sagen.

Version: 4.1

Fragen:
Flussnetzwerke:
1.1) Sei G ein Flussnetzwerk. Bei der Definition des Restnetzwerkes G_f können wir ohne Beschränkung der Allgemeinheit davon ausgehen, dass G keine entgegengesetzten Kanten hat. Warum?

1.2) Kann ein Restnetzwerk Kanten mit negativer Kapazität enthalten?

1.3) Was ist der entscheidende Unterschied zwischen der Definition der Kapazität eines Schnittes und der Definition des Flusses über einen Schnitt?

1.4) Ist jeder maximale Fluss ganzzahlig? Also f(e) \in \mathbb{N} \ \forall e \in E falls f maximal ist.

1.5) Ist Ford-Fulkerson (mit Tiefensuche) \in \mathsf{P}? Warum (nicht)?

1.6) Wie lautet die Laufzeitschranke für Ford-Fulkerson mit Breitensuche und wie lässt sie sich begründen?

1.7) Weshalb muss ein Sperrfluss im Niveaunetzwerk nicht immer zwangsweise ein maximaler Fluss sein? Beispiel andeuten.

Min-Cost-Flow:
2.1) Wie kann das Min-Cost-Flow Problem mit gegebenem W und l(e)=0 \forall e\in E einfach auf das Max-Flow Problem reduziert werden?

2.2) Begründe kurz, warum wenn ein Fluss nicht kostenoptimal ist, dann folgt, dass eine Zirkulation im Restnetzwerk existiert.

Matchings:
3.1) Was ist der Unterschied zwischen einem maximalen Matching und einem maximum Matching?

3.2) Warum liefert die Reduktion von einem bipartiten Matching Problem auf ein Flussproblem durch Einfügen von Quelle und Senke mit dem Max-Flow auch immer ein maximum Matching?

3.3) Welche Laufzeit ergibt sich für die in 3.2 genannte Methode Matchingprobleme zu lösen?

3.4) Wenn M ein Matching ist und ein verbessernder Pfad höchstens x Kanten aus M enthält, was lässt sich dann über die Länge des Pfades sagen?

Lineare Programme:
4.1) Warum muss der Schnitt zweier konvexer Polyhedrone wieder konvex sein?

4.2) Wie ist zu begründen, dass eine zulässige Basislösung einem Knoten des Lösungspolyhedrons entspricht?

4.3) Angenommen eine Basisvariable nimmt den Wert 0 an. Was können wir schließen?

4.4) Welche Informationen liefert der Vektor der reduzierten Kosten?

4.5) Warum suchen wir beim Simplexalgorithmus beim Bestimmen der Ausgangspivotspalte das Minimum von \left\{\frac{\hat b_k}{\hat a_{kj}}\mid \hat a_{kj} > 0\right\}?

4.6) Beim Erstellen des Hilfs-LPs müssen wir das LP zunächst auf eine Form b \geq 0 bringen. Warum?

Approximationsalgorithmen:
5.1) Wie kann man Set Cover auf Hitting Set reduzieren?

5.2) Wie kann man (zum Beweis, dass TSP nicht \alpha(n)-approximierbar sein kann für jedes polynomiell berechenbare \alpha(n)) mit Hilfe einer solchen hypothetisch existierenden Approximation das Hamiltonkreisproblem lösen?

5.3) Gebe zwei untere Schranken für den Makespan eines optimalen Scheduling Algorithmus' für das Scheduling auf identischen Maschinen an.

5.4) Beschreibe den Unterschied zwischen einem PTAS und einem FPTAS.


Antworten:
1.1 Falls G entgegengesetzte Kanten hätte, könnten wir in eine dieser einen Zwischenknoten einbauen. Es gibt dann einen Kreis, aber keine entgegengesetzten Kanten mehr

1.2) Nein, nur die Richtung kann sich umdrehen.

1.3) Bei der Kapazität, werden nur Kanten von Q nach S aufsummiert. Beim Fluss über den Schnitt werden die Rückkanten abgezogen.

1.4) Nein! Korollar 5 besagt "Für jeden maximalen Fluss gibt es einen ganzz. Fluss mit gleichem Wert". Bsp:
G = (V,E,q,s,c) mit V = \{q,a,b,s\} und E = \{(q,b),\ (q,a),\ (a,b),\ (b,s)\} und c(e) = 1\ \forall e\in E
In diesem Flussnetzwerk gibt es einen Fluss mit Wert 1, der aber über die Kanten (q,a),\ (q,b),\ (a,b) nur jeweils 0.5 Einheiten fließen lässt. Dies ist zulässig, da der Fluss definiert ist als f:E\to \mathbb{R}_0^+

1.5) Nein, FF hat mit Tiefensuche keine polynomielle Laufzeit, sondern nur eine pseudopolynomielle Laufzeitschranke durch \mathcal{O}(m\cdot C), wobei C die Summe der Kapazitäten aller Kanten ist.
Beispiel für ein solches Flussnetzwerk:
Bild

1.6) FF mit Breitensuche ist in \mathcal{O}(m\cdot nm) zu schaffen. m, da eine Iteration nach wie vor \mathcal{O}(m) lang dauert.
Kanten können gelöscht und wieder eingefügt werden. Eine Kante kann aber höchstens \frac{1}{2}n mal entfernt werden es gibt im Restnetzwerk bis zu 2m Kanten. Da in jeder Iteration mindestens eine Kante entfernt wird ist die Anzahl der Iterationen höchstens \frac{1}{2}n\cdot 2m = nm.

1.7) Beispiel: n parallele Kantenzüge von Quelle zu Senke. Zusätzlich vom obersten Kantenzug zum untersten diagonale Kanten,die alle Züge blockieren, falls etwas hindurchfließt. Dies ist dann ein nicht maximaler Sperrfluss.

2.1) Wir fügen von der alten Senke eine Kante zu einer neuen Senke ein, die die Kapazität W hat. Eine Lösung für das Max-Flow Problem liefert uns dann einen Fluss mit Wert W falls möglich.

2.2) Wenn ein Fluss f^* mit gleichem Wert existiert, so lässt sich der Differenzfluss (f^*-f) bilden, welcher offensichtlich den Wert 0 hat. Daraus folgt direkt, dass dieser eine Zirkulation ist. Dass sich diese Zirkulation in Kreise teilen lässt, wovon mindestens einer negative Kosten hat, falls f^* kostenoptimaler ist als f muss getrennt gezeigt werden.

3.1) Ein Matching ist (inklusions-)maximal, wenn man keine Kante mehr hinzufügen kann, ohne dass dann es kein Matching mehr ist. Ein Matching ist ein maximum Matching, wenn es kein Matching mit mehr Kanten gibt.

3.2) Es gibt eine bijektive Abbildung zwischen Matchingproblemen und Flussnetzwerken. Außerdem entspricht der Wert des Flusses der Kardinalität des Matchings. Es folgt die Annahme.

3.3) Mit dem Algorithmus Maximum-Matching 1 haben wir gezeigt, dass wir das bipartite Matchingproblem in \mathcal{O}(mn) lösen können. Wir haben auch festgestellt, dass der Algorithmus in jeder Iteration flussvergrößernde Wege sucht und somit Ford-Fulkerson entspricht. Also hat auch Ford-Fulkerson auf bipartiten Matchings eine Laufzeit von nur \mathcal{O}(mn).

3.4) Der Pfad hat höchstens Länge 2x+1, da er alternierend Nichtmatchingkanten und Matchingkanten besucht und mit freien Knoten beginnt und endet.

4.1) Angenommen der Schnitt A \cap B wäre nicht konvex. Dann gäbe es x,y \in A\cap B, sodass ein Punkt p auf der Verbindungslinie von x und y nicht in A \cap B wäre. p ist also entweder nicht in A oder nicht in B. O.B.d.A sei p nicht in A. Da aber x und y offensichtlich in A sind, würde folgen, dass A nicht konvex ist. Widerspruch!

4.2) Die Nichtbasisvariablen haben stets den Wert 0. Es gibt n-m = d Nichtbasisvariablen, denen man jeweils eine Nebenbedingung zuordnen kann. Also liegt die Basislösung auf dem Schnitt von mindestens d Hyperebenen, was einem Knoten des Polyhedrons entspricht.

4.3) Das LP ist degeneriert. Es schneiden sich mehr als d Hyperebenen in einem Knoten.

4.4) Er gibt für jede Nichtbasisvariable an, wie sich der Zielfunktionswert in Abhängigkeit dieser Variable ändert. Ist der Wert positiv, so können wir den Zielfunktionswert verbessern, indem wir die Variable in unsere Basis aufnehmen. Sind alle Einträge negativ, haben wir eine optimale Lösung erreicht.

4.5) Die Gleichung x_{B(i)} = \hat b_i - \hat a_{ij} x_j gibt uns für jede Basisvariable i an, welchen Wert sie beim Erhöhen der (Noch-)Nichtbasisvariable x_j annimmt. Offensichtlich erhöhen Basisvariablen mit negativem \hat a_{ij} ihren Wert und Basisvariablen mit positivem \hat a_{ij} verringern ihren Wert beim Erhöhen von x_j. (Das Erhöhen von x_j entspricht dem Entlanglaufen an einer Kante von einem Knoten/Basislösung zum/zur nächsten).
Mit dem Minimum von \left\{\frac{\hat b_k}{\hat a_{kj}}\mid \hat a_{kj} > 0\right\} bestimmen wir die Basisvariable, welche beim Erhöhen von x_j als erste den Wert 0 annimt (bevor sie negativ wird). So stellen wir sicher, dass wir x_j nicht zu weit erhöhen und die Lösung so durch eine negative Basisvariable ungültig machen. Wir suchen also den nächsten Knoten auf der gewählten Kante. Wenn wir x_j auf dieses Minimum setzen ergibt sich:
x_{B(i)} = \hat b_i - \hat a_{ij}\cdot\frac{\hat b_i}{\hat a_{ij}} = 0

4.6) Diese Form ist nötig, damit wir sicher gehen können, dass die initiale Basis, die aus den Hilfsvariablen besteht gültig ist. Wäre das b einer Bedingung negativ, so wäre die (aus dem Null-setzen der Nichtbasisvariablen resultierende) Bedingung mit h_i = b_i wegen h_i \geq 0 nicht erfüllbar.

5.1) Die Knoten aus dem Set Cover Problem (Fähigkeiten) werden zu Hyperkanten von Hitting Set. Die Teilmengen aus Set Cover werden zu Knoten in Hitting Set, wobei diese Knoten genau dann zu einer Hyperkante gehören, wenn sie in der Set Cover Eingabe die entsprechende Fähigkeit abdecken.

5.2) Man erstellt aus der Hamiltonkreiseingabe einen vollständigen Graphen. Die Kosten der Kanten werden auf 1 gesetzt, falls die Kante in der Eingabe war, ansonsten auf n\cdot\alpha(n). Findet der Approximationsalgorithmus eine TSP-Tour der Länge n, so gibt es einen Hamiltonkreis.
Zusatzfrage: Warum kann es nicht passieren, dass \alpha(n)=\frac{1}{n} und so immer eine TSP-Tour der Länge n ausgegeben wird?

5.3) opt \geq \frac{1}{m}\sum_{i\in[n]}p_i und opt \geq \max_{i\in[n]}(p_i)

5.4) Ein PTAS (Polynomial Time Approximation Scheme) ist ein Algorithmus der für jedes \varepsilon >0 eine (1 \pm \varepsilon)-Approximaion in zur Eingabelänge polynomiell beschränkter Zeit liefert. Ist die Zeit zusätzlich polynomiell in \frac{1}{\varepsilon} beschränkt, so nennen wir den Algorithmus einen FPTAS (Fully Polynomial Time Approximation Scheme).
Zuletzt geändert von philipp am 22.07.08 11:39, insgesamt 1-mal geändert.
Benutzeravatar
philipp
 
Beiträge: 394
Registriert: 05.11.06 23:36
Studiengang: Informatik (M.Sc.)
Studiert seit: WS 07/08
Anwendungsfach: Medizin

Beitragvon Stasik » 21.07.08 22:22

1.5 und 1.6 fehlt die Begründung für O(m), die Laufzeit folgt aus dem Zusammenhängen der Flussnetzwerke.

2.2. ich persönlich halte "kostenoptimaler" für total verwirrend!
3 Träume des Studenten:
Während der Vorlesungen: Mann, wann werde ich endlich essen!
Während des Praktikums: Mann, wann werde ich endlich schlafen!
Während der Klausurphase: Mann, wann werde ich endlich sterben!
Benutzeravatar
Stasik
 
Beiträge: 419
Registriert: 11.04.06 18:16
Studiengang: Informatik (Dipl.)
Studiert seit: SS 06
Anwendungsfach: E-Technik

Beitragvon Rowen » 05.08.08 20:10

philipp hat geschrieben:1.7) Weshalb muss ein Sperrfluss im Niveaunetzwerk nicht immer zwangsweise ein maximaler Fluss sein? Beispiel andeuten.
1.7) Beispiel: n parallele Kantenzüge von Quelle zu Senke. Zusätzlich vom obersten Kantenzug zum untersten diagonale Kanten,die alle Züge blockieren, falls etwas hindurchfließt. Dies ist dann ein nicht maximaler Sperrfluss.


Hi Phillip,

könntest du das Beispiel vielleicht mit einer Grafik erläutern?
Ich steige bei der sprachlichen Beschreibung jedenfalls nicht durch, wie das gemeint ist.

Gruß
Rowen
Rowen
 
Beiträge: 7
Registriert: 07.05.07 11:07
Wohnort: Aachen

Beitragvon philipp » 05.08.08 20:29

Rowen hat geschrieben:
philipp hat geschrieben:1.7) Weshalb muss ein Sperrfluss im Niveaunetzwerk nicht immer zwangsweise ein maximaler Fluss sein? Beispiel andeuten.
1.7) Beispiel: n parallele Kantenzüge von Quelle zu Senke. Zusätzlich vom obersten Kantenzug zum untersten diagonale Kanten,die alle Züge blockieren, falls etwas hindurchfließt. Dies ist dann ein nicht maximaler Sperrfluss.


Hi Phillip,

könntest du das Beispiel vielleicht mit einer Grafik erläutern?
Ich steige bei der sprachlichen Beschreibung jedenfalls nicht durch, wie das gemeint ist.

Gruß
Rowen

Bild
Benutzeravatar
philipp
 
Beiträge: 394
Registriert: 05.11.06 23:36
Studiengang: Informatik (M.Sc.)
Studiert seit: WS 07/08
Anwendungsfach: Medizin

Beitragvon Rowen » 05.08.08 21:13

Super, danke.
Rowen
 
Beiträge: 7
Registriert: 07.05.07 11:07
Wohnort: Aachen

Re: [Effiziente Algorithmen] Überblick über den Stoff, SS 08

Beitragvon panky » 29.05.10 19:24

1.6) FF mit Breitensuche ist in \mathcal{O}(m\cdot nm) zu schaffen. m, da eine Iteration nach wie vor \mathcal{O}(m) lang dauert.
Kanten können gelöscht und wieder eingefügt werden. Eine Kante kann aber höchstens \frac{1}{2}n mal


kann jemand mir noch mal kurz erklären:

kurz die Überlegung

1 - zwischen jedem Entfernen und Wierdeinfügen einer Kante $(u,v)$ erhöht sich die Distanz von der Quelle zum Knoten $u$ also um den additiven Wert 2. Da dimaximale Distanz $n-1$ ist, .....

warum eine kante höchstens \frac{1}{2}n mal gelöscht werden kann?
panky
 
Beiträge: 38
Registriert: 30.03.07 11:33


Zurück zu Theoretische Informatik / Theoretical Foundations