Online and Approximation Algorithms


  • Lecturer:
    Prof. Dr. Susanne Albers
  • Module:
    IN2304, TUMonline
  • Area:
    4+2 SWS in the area Informatik III (Theoretical Computer Science)
  • Time and Location:
  • Exercises:
    Wednesday, 12:00–14:00, 01.07.023
    Attention: On July 6th, there will be no Exercise session. The problem sets 11 and 12 will be discussed in the Exercise session of July, 13th.
    Teaching Assistants:
    Dr. Suzanne van der Ster, Dario Frascaria
  • Audience:
    Graduate students of computer science
    Students with computer science as minor
  • ECTS: 8 Points
  • Prerequisites:
    1st and 2nd year courses
    Course Efficient Algorithms and Data Structures I (IN2003) is advantageous but not required.
  • Exam:


In the international algorithms community one research focus over the past years has been the design of online and approximation algorithms. Here the general goal is to develop approximate solutions to problems for which the computation of exact solutions is hard or even impossible.

Online algorithms

Classical algorithm theory assumes that, for a given problem, all data is known in advance. However, in practice, many problems are online, i.e. relevant input arrives incrementally over time. We will design algorithms that can cope with the handicap of not knowing the future. We will study problems in data structuring, the resource management in operating systems, robotics and large networks.

Approximation algorithms

Many optimization problems that arise in practice are NP-hard. Assuming that P is not equal NP, these problems cannot be solved optimally in polynomial time. Again, one resorts to approximations. Of particular interest are polynomial time approximation schemes that compute (1+epsilon)-approximations, for any epsilon > 0, in polynomial time. We will study approximation algorithms for classical optimization problems.

Emphasis of the course, beside algorithm design, it the careful and thorough mathematical analysis of the various strategies and solutions.


Slides are available here.


  • 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

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 Theoretische Informatik
Prof. Dr. Susanne Albers

Boltzmannstr. 3
85748 Garching bei München

Tel +89.289.17706
Fax +89.289.17707