LTI
LTI

Sarntal-Kurs Moderne Algorithmik: Randomisiert, online, approximativ

Themenliste Prof. Albers

  1. Selforganizing Data Structures
    • D.D. Sleator, R.E. Tarjan. Amortized efficiency of list update and paging rules. Commun. ACM, 28(2): 202-208, 1985. PDF doi:10.1145/2786.2793
    • N. Reingold, J. Westbrook, D.D. Sleator. Randomized competitive algorithms for the list update problem. Algorithmica 11(1):15-32, 1994. PDF doi:10.1007/BF01294261

  2. Paging and Caching
  3. Scheduling: Makespan Minimization
    • V.V. Vazirani. Approximation Algorithms. Springer Verlag, Berlin, 2001, pages 79-83.PDF doi:10.1007/978-3-662-04565-7
    • L.A. Hall. Approximation algorithms for scheduling. Chapter 1, page 14. In Approximation Algorithms for NP-hard Problems, edited by D.S. Hochbaum, PWS Publishing Co., 1996.
    • M. Englert, D. Özmen, M. Westermann. The power of reordering for online minimum makespan scheduling. SIAM J. Comput., 43(3):1220-1237, 2014.PDF doi:10.1137/130919738

  4. Power Management
    • S. Irani, S. K. Shukla, R. K. Gupta. Online strategies for dynamic power management in systems with multiple power-saving states. ACM Trans. Embedded Comput. Syst., 2(3): 325-346, 2003. PDF doi:10.1145/860176.860180
    • J. Augustine, S. Irani, and C. Swamy. Optimal power-down strategies. SIAM J. Comput., 37(5): 1499-1516, 2008. PDF doi:10.1137/05063787X

  5. Online Matching
    • R.M. Karp, U.V. Vazirani, V.V. Vazirani. An optimal algorithm for on-line bipartite matching. Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 352-358, 1990. PDF doi:10.1145/100216.100262
    • B. Birnbaum, C. Mathieu. On-line bipartite matching made simple. SIGACT News, 39(1):80-87, 2008. PDF doi:10.1145/1360443.1360462
    • A. Mehta, A. Saberi, U.V. Vazirani, V.V. Vazirani. AdWords and generalized online matching. J. ACM, 54(5) 22, 2007. PDF doi:10.1145/1284320.1284321

  6. Min-Cut
    • D.R. Karger, C. Stein. A New approach to the minimum cut problem. J. ACM 43(4): 601-640, 1996. PDF doi:10.1145/234533.234534
      Material also in R. Motwani, P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995, pages 7-9 and 289-295.PDF
    • M. Stoer, F. Wagner. A simple min-cut algorithm. Journal of the ACM. 44(4):585, 1997. PDF doi:10.1145/263867.263872

  7. The Probabilistic Method
    • M. Mitzenmacher, E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005, pages 126-134.

  8. Energy Conservation in Data Centers
    • S. Albers. On energy conservation in data centers. Proc. 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA17), 2017. PDF
    • M. Lin, A.Wierman, L.L.H. Andrew, E. Thereska. Dynamic right-sizing for power-proportional data centers. IEEE/ACM Trans. Net., 21(5):1378-1391, 2013. PDF doi:10.1109/TNET.2012.2226216

  9. Refined Input Models
    • S. Albers, D. Frascaria. Quantifying competitiveness in paging with locality of reference. Proc. 42nd International Colloquium on Automata, Languages, and Programming (ICALP15), Springer LNCS 9134, 26-38, 2015. PDF doi:10.1007/978-3-662-47672-7_3
    • S. Albers, S. Lauer. On list update with locality of reference. J. Comput. Syst. Sci., 82(5):627-653, 2016. PDF doi:10.1007/978-3-540-70575-8_9

Themenliste Prof. Wanka

  1. Fundamentals of Optimization Problems
    • G. Ausiello, P. Grescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi. Complexity and Approximation - Combinatorial Problems and Their Approximability Problems. pp. 22-38 PDF, pp. 87-152 PDF. Springer-Verlag: Berlin-Heidelberg-New York, 1999.
    • J. Hromkovič. Algorithmics for Hard Problems - Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. pp. 213-238 PDF. Springer-Verlag: Berlin-Heidelberg-New York, 2001.
    • R. Wanka. Approximationsalgorithmen - Eine Einführung. pp. 81-85 PDF. B. G. Teubner Verlag: Wiesbaden, 2006.

  2. The Knappsack Problem
    • J. Hromkovič. Algorithmics for Hard Problems - Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. pp. 238-248 PDF. Springer-Verlag: Berlin-Heidelberg-New York, 2001.

  3. Dynamic Programming for Counting the Number of Knapsack Solutions
    • M. Dyer. Approximate counting by dynamic programming. pp. 693-699 PDF. In: Proc. 35th ACM Symp. on Theory of Computing (STOC), 2003. 10.1145/780542.780643.
    • P. Gopalan, A Klivans, R. Meka, D. Stefankovic, S. Vempala, E. Vigoda. An FPTAS for #Knapsack and Related Counting Problems. pp. 817-826 PDF. In: Proc. 52nd IEEE Symp. on Foundations of Computer Science (FOCS), 2011. doi:10.1109/FOCS.2011.32.

  4. Particle Swarm Optimization (PSO) and Parameter Selection
    • M. Jiang, Y. P. Luo, S. Y. Yang. Particle Swarm Optimization - Stochastic Trajectory analysis and parameter selection. pp. 179-198 PDF. Swarm Intelligence - Focus on Ant and Particle Swarm Optimization, 2007.
    • For background information also refer to: Sabine Helwig. Particle Swarms for Contrained Optimization. (full text is available here). Ph.D. Thesis, University of Erlangen-Nuremberg, 2010.

  5. Particle Swarm Optimization for Discrete Problems (PSO) (reserviert)
    • M. Mühlenthaler, A. Raß, M. Schmitt, A. Siegling, R. Wanka. Runtime Analysis of a Discrete Particle Swarm Optimization Algorithm on Sorting and OneMax. pp. 13-24 PDF. Conference on Foundations of Genetic Algorithms 2017. doi: 10.1145/3040718.3040721.

  6. Evolutionary Algorithms for Minimum Spanning Trees (EA)
    • F. Neumann, I. Wegener. Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. pp. 32-40 PDF. Theoretical Computer Science 378, 2007. doi:10.1016/j.tcs.2006.11.002.

  7. The Satisfiability Problem: Random Walk and Derandomization
    • U. Schöning. A Probabilistic algorithm for k-SAT based on limited local search and restart. pp. 615-623 PDF. Algorithmica 32, 2002. Paper beim Autor.
    • R. A. Moser, D. Scheder. A Full Derandomization of Schöning's k-SAT Algorithm. pp. 245-251 PDF. In: Proc. 43rd ACM Symp. on Theory of Computing (STOC), 2011. doi:10.1145/1993636.1993670.

  8. Constructive Proof of the Lovasz Local Lemma
    • H. Gebauer, R. A. Moser, D. Scheder, E. Welzl. The Lovasz Local Lemma and Satisfiability. pp. 30-54 PDF. Efficient Algorithms - Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday, 2009. doi:10.1007/978-3-642-03456-5_3.

  9. Approximate Counting: The Number of Colorings (reserviert)
    • R. Wanka. Approximationsalgorithmen - Eine Einführung. pp. 151-189 PDF. Teubner, 2006.


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