LTI
LTI

Seminar: Selected Topics in Efficient Algorithms

General Information

Content

This seminar addresses Master's students in Computer Science with a scientific interest in the design and analysis of algorithms. The seminar participants will work on selected (research) literature. The papers cover a spectrum of topics, including (a) computational geometry, (b) graph algorithms, (c) algorithmic game theory, and (d) energy-efficient algorithms.

Seminar Topics

  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. 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.
  7. 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.
  8. 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.
  9. Network Design: Arbitrary Payments
    E. Anshlevich, A. Dasgupta, E. Tardos and T. Wexler. Near optimal network design with selfish agents. Theory of Computing, 4(1):77-109, 2008.
  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.
  13. Approximation Algorithms: Basics
    T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms. 3rd Edition. MIT Press 2009. ISBN 978-0-262-03384-8. Chapter 35.
  14. Approximation Algorithms: Greedy and Local Search
    D.P. Williamson and D.B. Shmoys. The Design of Approximation Algorithms.. Cambridge University Press 2011. ISBN ISBN 978-0-521-19527-0. Chapter 2.


July 2022: Jens Quedenfeld completed his doctoral degree.

June 2022: Maximilian Janke completed his doctoral degree.

March 2022: Alexander Eckl completed his doctoral degree.

June 2021: Leon Ladwig completed his doctoral degree.

February 2020: The Program Committee of SWAT 2020 is chaired by Susanne Albers.

February 2020: Susanne Albers is invited speaker at the ACM India Annual Event.

ESA/ALGO 2019 will be organized by Susanne Albers and her group.

May 2019: Susanne Albers is invited speaker at the symposium 50 Years Informatics

July 2019: Susanne Albers is invited speaker at SIROCCO 2019, Italy.

December 2017: Susanne Albers will give keynote address at the Graduation Day, Department of Computer Science at RWTH Aachen University.

April 2017: New Research Training Center AdONE, funded by the German Research Foundation.

Susanne Albers receives ERC Advanced Grant. Press release of the Bavarian State Ministry of the Sciences, Research and the Arts.

August 2016: Susanne Albers is keynote speaker at Euro-Par 2016, Grenoble.

Susanne Albers, Nicole Megow and Andreas S. Schulz will organize MAPSP 2017.

Juni 2016: Susanne Albers gives an invited lecture at the Academy of Sciences and Literature, Mainz.

September 2015: Susanne Albers is invited speaker at MPI-INF – 25th Anniversary. The program features several Turing Award winners, Leibniz Prize winners, Humboldt Prize winners and ERC Grant winners.

June 2015: Susanne Albers is keynote speaker at the 31st International Symposium on Computational Geometry (SOCG15), Eindhoven.

June 2015: Susanne Albers is invited speaker of the tutorial on Network Creation Games: How Does the Internet Form? organized by Erik D. Demaine (MIT) and 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
News