LTI
LTI

Seminar: Ausgewählte Themen aus Effiziente Algorithmen

  • Dozent: Prof. Dr. Susanne Albers
  • Modul: IN2107, IN8901, TUMonline
  • Bereich:
    2 SWS Seminar im Bereich Informatik III (Theoretische Informatik)
  • Zeit und Ort:
    Das Seminar findet als Blockseminar im Februar 2023 statt.

Inhalt

Dieses Seminar richtet sich an Studierende im Masterstudiengang Informatik, die Interesse an der Entwicklung und Analyse von Algorithmen haben. Die Seminarteilnehmer arbeiten ausgewählte Literatur auf. Die vorgestellten Arbeiten behandeln ein Spektrum von Themen und kommen unter anderem aus den Bereichen (a) algorithmische Geometrie, (b) Graphenalgorithmen, (c) algorithmische Spieltheorie und (d) energieeffiziente Algorithmen.

Seminarthemen

  1. Computational Geometry: Convex Hulls
    M. de Berg, O. Cheong, M. van Kreveld and M. Overmars. Computational Geometry: Algorithms and Applications. 3rd Edition, Springer, 2008. Chapters 1 and 11, pp. 1-10 and 243-249.
  2. Computational Geometry: Line Segment Intersection
    M. de Berg, O. Cheong, M. van Kreveld and M. Overmars. Computational Geometry: Algorithms and Applications. 3rd Edition, Springer, 2008. Chapter 2, pp. 19-29.
  3. Computational Geometry: Point Location
    M. de Berg, O. Cheong, M. van Kreveld and M. Overmars. Computational Geometry: Algorithms and Applications. 3rd Edition, Springer, 2008. Chapter 6, pp. 121-137.
  4. Computational Geometry: Voronoi Diagrams
    M. de Berg, O. Cheong, M. van Kreveld and M. Overmars. Computational Geometry: Algorithms and Applications. 3rd Edition, Springer, 2008. Chapter 7, pp. 147-159.
  5. Online Matching in Bipartite Graphs
    R.M. Karp, U.V. Vazirani and V.V. Vazirani. An optimal algorithm for online bipartite matching. Proc. 22nd Annual ACM Symposium on Theory of Computing (STOC), 352-358, 1990.
    B.E. Birnbaum and C. Kenyon. Online bipartite matching made simple. SIGACT News, 39(1):80-87, 2008.
    N.R. Devanur, K. Jain and R.D. Kleinberg. Randomized primal-dual analysis of Ranking for online bipartite matching. Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 101-107, 2013.
  6. Adwords: Online Matching in Advertising
    A. Mehta, A. Saberi, U. Vazirani and V. Vazirani. AdWords and generalized online matching. Journal of the ACM, 54(5):22, 2007.
  7. Online Matching with Augmentations
    K. Chaudhuri, C. Daskalakis, R.D. Kleinberg and H. Lin. Online bipartite perfect matching with augmentations. Proc. 28th IEEE International Conference on Computer Communications (INFOCOM), 1044-1052, 2009.
  8. Opinion Formation in Social Networks
    F. Chierichetti, J. Kleinberg and A. Panconesi. How to schedule cascades in an arbitrary graph. SIAM Journal on Computing, 43(6):1602-1623, 2008.
  9. Network Design: Fair Cost Allocation
    E. Anshlevich, A. Dasgupta, J.M. Kleinberg, E. Tardos and T. Wexler. The price of stability in network design with fair cost allocation. SIAM Journal on Computing, 38(4):1906-1920, 2014.
  10. Network Creation Games
    A. Fabrikant, A. Luthra, E.N. Maneva, C.H. Papadimitriou and S. Shenker. On a network creation game. Proc. 22nd ACM Symposium on Principles of Distributed Computing (PODC), 347-351, 2003.
    N. Alon, E.D. Demaine, M.T. Hajiaghayi and T. Leighton Basic network creation games. SIAM Journal on Discrete Mathematics, 27(2):656-668, 2013.
  11. Power Management for a Single Device
    S. Irani, S.K. Shukla and R. Gupta. Algorithms for power savings. ACM Trans. Algorithms, 3(4):41, 2007.
    J. Augustine, S. Irani and C. Swamy. Optimal power-down strategies. SIAM J. Comput., 37(5):1499-1516, 2008.
  12. Dynamic Right-Sizing of Data Centers
    S. Albers. On Energy Conservation in Data Centers. ACM Transactions on Parallel Computing. 6(3): 13:1-13:26, 2019.

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