Kombinatorische Optimierung 2
SS 2015, 4 VO/1 UE (502.726/502.727)

Ausgewählte Kapitel der Diskreten Mathematik
SS 2015, 3 VO/1 UE (MAT.860/MAT.861)

E. Dragoti-Çela
Institut für Optimierung und Diskrete Mathematik

Zeit und Ort Vorlesung,

Zeit und Ort Übung,


• Beginn: Mo., 3.3.2015, 14:15-16:00, SR C208
• Vorlesungsinhalt

Diese Lehrveranstaltung befasst sich mit kombinatorischen Optimierungsproblemen, die in der LV 'Kombinatorische Optimierung 1' nicht behandelt wurden. In der Regel sind das NP-schwere Optimierungsprobleme für die sowohl strukturelle Eigenschaften als auch Lösungsansätze und Approximationsverfahren besprochen werden. Je nach Problem wir ein breiter Bogen gespannt: von Schranken und Heuristiken bis hin zu Approximationsalgorithmen, PTAS und FPTAS. Das Ziel ist, einerseits die Studierenden mit prominenten, sowohl theoretisch als auch praktisch relevanten Problemen der Kombinatorischen Optimierung vertraut zu machen, und anderseits eine Handvoll an Lösungsansätzen und algorithmischen Paradigmen als praktisch relevantes Wissen zu vermitteln.


Einige Kapitelüberschriften und Stichwörter sind:

• Matching Probleme in nicht bipartiten Graphen: das gewichtete Matching Problem, b-Matching, T-joins, geometrische Dualität und der Algorithmus von Goemans und Williamson.
• Grundzüge der Polyeder Kombinatorik, total dual integrality.
• Das Rundreiseproblem: untere Schranken, Heuristiken, Approximationsalgorithmen (PTAS/FPTAS) das Euklidische TSP, das TSP Polytop, Branch and Bound Verfahren
• Covering und Packing Probleme: Heuristiken und Approximationsalgorithmen
• Matroide Dualität, Schnitt von Matroiden, Gewichteter Schnitt von Matroiden, Greedoide
und wenn Zeit übrig bleibt
• Quadratische Zuordnungsprobleme: untere Schranken, Heuristiken
• Literatur
• W. Cook, W. Cunningham, W. Pulleyblank und A. Schrijver, Combinatorial Optimization, Wiley, 1998.
• G. Cornuejols, Combinatorial Optimization: Packing and covering, SIAM, 2001.
• D. Hochbaum (Hrsg.), Approximation Algorithms for NP-hard problems, PWS Publishing Company, 1997.
• B. Korte und J. Vygen, Kombinatorische Optimierung: Theorie und Algorithmen, Springer, 2008.
• E. Lawler (Hrsg.), The traveling salesman problem: a guided tour of combinatorial optimization, Wiley, 1992.
• Prüfungsmodus

Die Vorlesung wird anhand einer mündlichen Prüfung benotet. Die Prüfungstermine werden je nach Bedarf mit der Vortragenden vereinbart.

Die einstündige Übung hat einen immanenten Charakter und wird anhand von zwei Klausuren und der Mitarbeit der Studierenden in den Übungsstunden mit Hilfe eines Punktesystems benotet. Die wird in Doppelstunden organisiert, sodass ungefähr in jeder zweiten Semesterwoche eine Doppelstunde Übung stattfindet. Beginn am 20.3.!


Klausurtermine:

• 1. Übungsklausur: Montag, 11. Mai oder Mittwoch 13. Mai
• 2. Übungsklausur: Freitag, 3. Juli
• Nachklausur: In der letzen Woche der Semesterferien oder in der ersten Woche des Sommersemesters. Genauer Termin wird noch rechtzeitig bekanntgegeben.

Aufgrund des immanenten Charakters der Lehrveranstaltung gibt es genau eine Nachklausur. Beim Antreten zur Nachklausur ist zu entscheiden, ob die erste oder die zweite Klausur wiederholt werden soll. Durch den Antritt werden die Punkte aus der wiederholten Klausur gelöscht.


Die Klausuren werden (rechtzeitig) im Prüfungssystem des TUGonline erfasst, inkl. Angaben über Ort ud Zeit;
die Anmeldung zu den Klausuren erfolgt via TUGonline.


Bei den Übungsklausuren sind alle schriftlichen Unterlagen sowie Taschenrechner erlaubt. Dennoch sind alle Zwischenschritte anzugeben. Die Verwendung von internetfähigen Geräten, insbesondere Notebooks, PDAs, Handhelds, Handys etc., ist nicht gestattet.


Mitarbeit im Rahmen der Übungseinheiten:
Für ein positives Übungszeugnis muss jeder Studierender mindestens zwei Mal an der Tafel vorrechnen. Unter allen Kandidaten, die ein bestimmtes Beispiel vorrechnen möchten, wird unter Berücksichtigung der Anzhal der bereits getätigten Tafelmeldungen, eine Kandidatin bzw. ein Kandidat zur Vorführung and der Tafel ausgesucht. Jede Tafelmeldung ist maximal 2 Punkte Wert. Bei der Bewertung der Tafelmeldungen wird neben der mathematischen Korrektheit auch auf die Qualität der Präsentation Wert gelegt. Es können höstens 6 Punkte aufgrund von Tafelmeldungen erworben werden.


Bei jeder Klausur können maximal 16 Punkte erworben werden.
Somit ergibt sich eine maximale Anzahl von 38 zu erreichenden Punkten.
Für ein positives Übungszeugnis müssen bei den Klausuren in Summe mindestens 14 Punkte erreicht werden.


Es gibt auch die Möglichkeit Bonuspunkte zu erwerben: wenn für das Vorrechnen eines Beispiels keine Kandidatin/keinen Kandidaten gibt, die/der weniger als zweimal an der Tafel war, dann dürfen andere Freiwillige das Beispiel vorrechnen und maximal einen Punkt pro vorgerechnetem Beispiel erwerben. Es können maximal 2 Bonuspunkte erworben werden. Bonuspunkte können auch durch besonders aktive Mitarbeit, besonders schöne Lösungen, Präsentationen und/oder Ideen erworben werden.


Notenschlüssel für die Bewertung der Übung:

0 <= P <= 18	Nicht genügend
18 < P <= 23	Genügend
23 < P <= 27	Befriedigend
27 < P <= 31	Gut
31 < P	Sehr Gut.



• Übungsblätter (pdf)
  • 1. Übungsblatt; zu besprechen am Fr., 20.3.
  • 2. Übungsblatt; zu besprechen am Fr., 24.4.
  • 3. Übungsblatt; zu besprechen am Fr., 8.5.
  • 4. Übungsblatt; zu besprechen am Fr., 29.5.
  • 5. Übungsblatt; zu besprechen am Fr., 12.6.
  • 6. Übungsblatt; zu besprechen am Fr., 26.6.
  
  

• Sonstiges (pdf)
  • Algorithmus zur Ohrenzerlegung eines gegebenen faktorkritischen Graphen entsprechend zweier zu einem fast perfekten Matching gehörenden Funktionen μ und ψ aus Korte und Vygen, siehe Referenzliste oben.
  • Pseudocode des Edmonds Blossom Algorithmus zur Bestimmung eines Matchings mit maximaler Kardinalitä aus Korte und Vygen, siehe Referenzliste oben.
  • Das Gewichtete-Matching-Algorithmus;
    und seine Routinen
    Blütenweg , Baumweg und Update
    aus Korte und Vygen, siehe Referenzliste oben.

  ---

  
    cela@opt.math.tu-graz.ac.at.

  Back to my homepage

  Letzte Änderung: Juni 2015

  ---