Course content.


Topics

  • Computational complexity
  • Approximation algorithms
  • (F)PTAS
  • Online algorithms

Algorithmic approaches

  • Exact solutions and approximation algorithms for computationally hard problems
  • Online algorithms and competitive analysis

Current stuff.

  • There is a nice overview on proof techniques, all with a common example, from Estie Arkin available [here].
  • Welcome to the class!

Mailing list.

Information will be made available via the mailinglist, contact christiane.schmidt(at)liu.se to be added to the list.

Homework and Lectures.

  • The current homework sets can be found here.
  • Slides/notes can be downloaded from this site - Slides are password protected!
  • The password will be announced in the first seminar.

Literature.

The course is self-contained, that is, the lecture notes and other course material will be enough to follow the course. For the group presentation material will be made available. Interested students may use the following books for additional self-study:
  • •Vijay V. Vazirani: Approximation Algorithms
  • • Michael R. Garey , David S. Johnson: Computers and Intractability
  • •Borodin, El-Yaniv: Online Computation and Competitive Analysis