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!
  • •The first seminar of the course will take place on December 13, 9:30-13:15 on zoom.
  • •The second seminar of the course will take place on January 13, 13:00-17:00 on zoom.
  • •The homework-discussion seminar will take place on January 20, 13:00-15:00 on zoom.
  • •The third seminar of the course will take place on January 27, 9:30-13:30 on zoom.
  • •The fourth seminar of the course will take place on February 20, 13:00-17:00 on zoom.
  • •The fifth seminar of the course will take place on March 3, 13:00-17:00 on zoom.
  • •The sixth seminar of the course will take place on March 17, 12:30-16:30 on zoom.

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