LEA

  • Leitung:
    Prof. Dr. Harald Räcke
  • Modul: IN0014, IN2107, IN8901, TUMonline
  • Bereich:
    2 SWS Seminar im Bereich Informatik III (Theoretische Informatik)
  • Anmeldung:
    Für die Anmeldung muss der Student sich mit der Seminarleitung in Verbindung setzen. Die Studenten, die ein Thema bekommen haben, werden dann von der Seminarleitung in TUMonline angemeldet. Wer sicher einen Platz erhalten möchte, sollte zur Vorbesprechung erscheinen, da die dort erscheinenden Personen priorisiert werden. Falls ihr Interesse habt, meldet euch bitte zusätzlich kurz bei Harald Räcke (raecke@in.tum.de), damit die Teilnehmerzahl besser abgeschätzt werden kann.
  • Vorbesprechung:
    Montag, 27.1.2014; 12:00-13:00 im Seminarraum MI 03.11.018

Zusammenfassung

Viele Optimierungsprobleme, die in praktischen Anwendungen sehr oft vorkommen, sind NP-schwer. Wenn nun angenommen wird, dass die Problemklassen P und NP nicht gleich sind, dann ist die Lösung dieser Probleme aus praktischer Sicht nicht möglich - sie würde sehr viele Ressourcen (Zeit und evtl. Speicherplatz) in Anspruch nehmen.

Ein möglicher Ausweg aus diesem Dilemma bildet der Einsatz von Approximationsalgorithmen. Hierbei versucht man das gegebene Optimierungsproblem nicht mehr exakt zu lösen (da dieses ja höchstwahrscheinlich nicht in Polynomzeit möglich ist), sondern man versucht die optimale Lösung bestmöglich in Polynomzeit zu approximieren.

Im Rahmen dieses Seminars wird zunächst eine Einführung in das Gebiet der Approximationsalgorithmen erfolgen, und es werden allgemeine Approximationstechniken eingeführt. Darauf aufbauend werden dann Approximationsalgorithmen für verschiedene Probleme betrachtet. Der Schwerpunkt wird hierbei auf Graphproblemen liegen.

The seminar talks can be presented in German or English, depending on the preference of the students.

Themen

  1. Introduction: from NPO to APX
    [Vaz 01] Kapitel 1, [ACG+99] Kapitel 3.1
  2. Introduction to Linear Programming Techniques for Approximation Algorithms
    [Vaz 01] Kapitel 12
  3. Set Cover
    [Vaz 01] Kapitel 13-15, [WS 11] Kapitel 1.2-1.7
  4. Sparsest Cut
    [Vaz 01] Kapitel 21.1-21.5, [WS 11] Kapitel 15.1, (15.4)
  5. Applications of Sparsest Cut
    [Vaz 01] Kapitel 21.6, [LR 99]
  6. The Multicut Problem
    [Vaz 01] Kapitel 18,20, [WS 11] Kapitel 8.3
  7. The Multiway Cut Problem
    [Vaz 01] Kapitel 19, [WS 11] Kapitel 8.1,8.2
  8. Tree embeddings
    [WS 11] Kapitel 8.5,8.6
  9. An $O(log n)$-Approximation for Minimum Bisection
    [WS 11] Kapitel 15.2,15.3
  10. The Steiner Forest Problem
    [Vaz 01] Kapitel 22, [WS 11] Kapitel 7.4
  11. Euclidean TSP
    [Vaz 01] Kapitel 11, [WS 11] Kapitel 10
  12. Sorting by Reversals
    [BHK 02], [BP 96], [Heu 10], [Chr 98], [KS 95], [Cap 97]

Literatur

  • [ACG+99]
    G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi
    Complexity and Approximation,
    Springer, 1999.
  • [Vaz 01]
    Vijay V. Vazirani,
    Approximation Algorithms,
    Springer 2001
  • [WS 11]
    David P. Williamson and David B. Shmoys,
    The Design of Approximation Algorithms,
    Cambridge University Press 2011
  • [LR 99]
    Tom Leighton and Satish Rao.
    Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms.
    J. ACM 46, 6 (November 1999), 787-832. 1999.
  • [BHK 02]
    Piotr Berman, Sridhar Hannenhalli and Marek Karpinski.
    An 1.375-Approximation Algorithm for Sorting by Reversals.
    In Proceedings of ESA 2002.
  • [BP 96]
    Vineet Bafna and Pavel A. Pevzner.
    Genome Rearrangements and Sorting by Reversals.
    SIAM J. Comput., 25(2), 272-289. 1996.
  • [Heu 10]
    Volker Heun
    Skript zu Vorlesung Algorithmen und Sequenzen,
    2010.
  • [Chr 98]
    David A. Christie.
    A 3/2-approximation algorithm for sorting by reversals.
    In Proceedings of SODA '98, 244-252. 1998.
  • [KS 95]
    J. Kececioglu and D. Sankoff.
    Exact and Approximation Algorithms for Sorting by Reversals, with Application to Genome Rearrangement.
    Algorithmica, 13 (1-2), 180-210. 1995.
  • [Cap 97]
    Alberto Caprara.
    Sorting by reversals is difficult.
    In Proceedings of RECOMB '97. 75-83. 1997.