Online- und Approximationsalgorithmen
News
-
Die Vorlesung am Mittwoch, 09.07.2014 wurde auf den 07.07.2014 von 16-18 Uhr in Raum 02.13.010 verlegt.
-
Die Vorlesung am Mittwoch, 02.07.2014 entfällt
-
Die mündliche Klausur wird am 18.07.2014 stattfinden.
-
Aufgrund der Oster-Feiertage und der Fachschaftsversammlung am Mittwoch den 23. April wird es am 24. April von 14-16 Uhr einen zusätzlichen Vorlesungstermin in Raum 03.13.054 geben.
Vorlesung
- Dozent:
Prof. Dr. Susanne Albers
- Modul:
IN2304,
TUMonline
- Bereich:
4+2 SWS Vorlesung im
Bereich Informatik III (Theoretische Informatik)
Wahlpflichtvorlesung
im Gebiet Algorithmen
- Zeit und Ort:
Montag, 14:00–16:00, 00.08.038
Mittwoch, 10:00–12:00, 00.08.038
- Übung:
Mittwoch, 13:00–14:30, Raum 01.11.018
Übungsleitung:
Moritz Fuchs
- Hörerkreis:
Studierende im Hauptstudium der Informatik
Studierende mit Nebenfach Informatik
- ECTS: 8 Punkte
- Voraussetzungen:
Stoff des Informatik Grundstudiums
Vorlesung Effiziente Algorithmen und Datenstrukturen I vorteilhaft, aber nicht notwendig.
- Klausurtermin:
18.07.2014 (mündlich)
Inhalt
In der internationalen Algorithmenforschung bildet die Entwicklung von Online- und Approximationsalgorithmen seit geraumer Zeit einen Arbeitschwerpunkt.
Ziel ist die Entwicklung von Näherungslösungen für Probleme, die schwer oder gar nicht exakt gelöst werden können.
Online-Algorithmen
Der klassische Algorithmenentwurf geht davon aus, dass die zur Lösung eines Problems benötigten Daten zu Beginn der Berechnungen
vollständig vorliegen. In vielen praktischen Problemen treffen Eingabedaten jedoch online, d.h. nach und nach im Laufe der Zeit ein. Wir werden Algorithmen
entwickeln, die mit solchen Bedingungen fertig werden. Wir werden insbesondere Probleme in der Datenstrukturierung, der Ressourcenverwaltung auf
Betriebssystemebene, der Robotik und in großen Netzwerken untersuchen.
Approximationsalgorithmen
Viele Optimierungsprobleme in der Praxis sind NP-hart. Ziel ist wieder die Entwicklung von Näherungslösungen, die ein beweisbar gutes
Verhalten aufweisen. Von besonderem Interesse sind Approximationsschemata, die in polynomieller Zeit (1+e)-Approximationen erzielen, wobei e > 0 beliebig ist.
Wir werden Approximationsalgorithmen für klassische Optimierungsprobleme entwerfen.
Neben dem Algorithmenentwurf liegt der Schwerpunkt der Veranstaltung auf der gründlichen mathematischen Analyse der vorgestellten Strategien und Lösungen.
Folien
Folien zu Online-Algorithmen sind hier verfügbar (werden jede Woche ergänzt).
Literatur
- A. Borodin und R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, Cambridge, 1998. ISBN 0-521-56392-5
- V.V. Vazirani. Approximation Algorithms. Springer Verlag, Berlin, 2001. ISBN 3-540-65367-8
Dezember 2025: Sebastian Schubert hat seine Promotion abgeschlossen..
Juli 2025: Ruslan Zabrodin hat seine Promotion abgeschlossen.
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.
