LTI
LTI

Seminar / Masterseminar: Approximationsalgorithmen

  • Leitung:
    Prof. Dr. Harald Räcke
  • Modul: IN0014, IN2107, IN8901, TUMonline
  • Bereich:
    2 SWS Seminar im Bereich Informatik III (Theoretische Informatik)
  • Vorbesprechung:
    Donnerstag, 1.2.2018; 16:00-17:00 im Seminarraum 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] Chapter 1, [ACG+99] Chapter 3.1
  2. Introduction to Linear Programming Techniques for Approximation Algorithms
    [Vaz 01] Chapter 12
  3. Set Cover
    [Vaz 01] Chapter 13-15, [WS 11] Chapter 1.2-1.7
  4. Sparsest Cut
    [Vaz 01] Chapter 21.1-21.5, [WS 11] Chapter 15.1, (15.4)
  5. Applications of Sparsest Cut
    [Vaz 01] Chapter 21.6, [LR 99]
  6. The Multicut Problem
    [Vaz 01] Chapter 18,20, [WS 11] Chapter 8.3
  7. The Multiway Cut Problem
    [Vaz 01] Chapter 19, [WS 11] Chapter 8.1,8.2
  8. Tree embeddings
    [WS 11] Chapter 8.5,8.6
  9. An $O(log n)$-Approximation for Minimum Bisection
    [WS 11] Chapter 15.2,15.3
  10. Graph Partitioning Using Single Commodity Flows
    [KRV 09]
  11. The Steiner Forest Problem
    [Vaz 01] Chapter 22, [WS 11] Chapter 7.4
  12. Steiner Network
    [Vaz 01] Chapter 23, [WS 11] Chapter 11.3
  13. Euclidean TSP
    [Vaz 01] Chapter 11, [WS 11] Chapter 10
  14. Max Cut
    [Vaz 01] Chapter 26 (in particular 26.4), [WS 11] Chapter 6 (in particular 6.2)
  15. 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.
  • [KRV 09]
    Graph Partitioning Using Single Commodity Flows
    Rohit Khandekar, Satish Rao, Umesh Vazirani JACM 56 (4), pages 385-390. 2009.
  • [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.

Juli 2022: Jens Quedenfeld hat seine Promotion abgeschlossen.

Juni 2022: Maximilian Janke hat seine Promotion abgeschlossen.

March 2022: Alexander Eckl hat seine Promotion abgeschlossen.

Juni 2021: Leon Ladewig hat seine Promotion abgeschlossen.

Februar 2020: Susanne Albers ist Vorsitzende des Programmkomitees der SWAT 2020.

Februar 2020: Susanne Albers ist eingeladene Sprecherin auf dem ACM India Annual Event.

ESA/ALGO 2019 wird von Susanne Albers und ihrer Gruppe organisiert.

Juli 2019: Susanne Albers ist Festrednerin der Tagung SIROCCO 2019, Italien.

Mai 2019: Susanne Albers ist Festrednerin des Symposiums 50 Years Informatics

Dezember 2017: Susanne Albers hält Festvortrag am Tag der Informatik, Absolventenfest der RWTH Aachen.

April 2017: Neues DFG Graduiertenkolleg AdONE.

Susanne Albers erhaelt ERC Advanced Grant. Pressemitteilung Bayerisches Staatsministerium f. Bildung u. Kultus, Wissenschaft u. Kunst.

August 2016: Susanne Albers hält einen Plenarvortrag auf Euro-Par 2016, Grenoble.

Susanne Albers, Nicole Megow und Andreas S. Schulz organisieren MAPSP 2017.

Juni 2016: Susanne Albers hält einen eingeladenen Vortrag in der Akademie der Wissenschaften und der Literatur, Mainz.

September 2015: Susanne Albers ist eingeladene Sprecherin auf dem MPI-INF – 25th Anniversary. Vortragende im Programm sind mehrere Turing-Preisträger, Leibniz-Preisträger, Humboldt-Preisträger und Gewinner von ERC Grants.

Juni 2015: Susanne Albers hält einen Plenarvortrag auf dem 31st International Symposium on Computational Geometry (SOCG15), Eindhoven.

Juni 2015: Susanne Albers ist eingeladene Sprecherin des Tutorials Network Creation Games: How Does the Internet Form?, organisiert von Erik D. Demaine (MIT) und MohammadTaghi Hajiaghayi (University of Maryland). 16th Conference on Electronic Commerce (EC15), Portland, Oregon.

Lehrstuhl für Algorithmen und Komplexität
Prof. Dr. Susanne Albers

Boltzmannstr. 3
85748 Garching bei München

Tel +89.289.17706
Fax +89.289.17707

E-Mail
Aktuelles