LEA

Online and Approximation Algorithms

News

  • The class on July 9 was moved to July 7 from 4-6pm in room 02.13.010.
  • There will be no class on July 2, 2014.
  • The oral exam will be held on July 18, 2014.
  • Due to the easter holidays and the student's meeting on Wednesday April 23 there will be another lecture on Thursday, April 24 in room 03.13.054.

Course

  • Leitung:
    Prof. Dr. Susanne Albers
  • Module: IN2304, TUMonline
  • Area:
    4+2 SWS in the area Informatik III (Theoretical Computer Science)
  • Time and Location:
    Monday, 14:00–16:00, 00.08.038
    Wednesday, 10:00–12:00, 00.08.038
  • Exercises:
    Wed, 1pm–2:30pm, Room 01.11.018
    Teaching Assistant: Moritz Fuchs
  • 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 is advantageous but not required.
  • Exam:
    July 18, 2014 (oral)

Content

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

Slides on online algorithms available here (extended each week).

Literature

  • 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