PhD course: Design and Analysis of Algorithms Part 2- Approximation and Online Algorithms, fall 2018.

This course is the second in a series of three, where each course can be taken independently:
Part 1: Mathematical Tools and Network Problems (homepage for part 1)
Part 2: Approximation and Online Algorithms
Part 3: Computational Geometry

Organisation

  • Lecturer: Christiane Schmidt
  • • The first seminar (Sem1) is on September 6, 2018, 13:00-17:00, in SP6225.
  • • The second (2-hour) seminar on homework discussion will take place October 4, 2018, 15:00-17:00, in SP6225.
  • • The third, full, seminar (Sem2) will take place Oct 18, 13:00-17:00, in SP6225.
  • • There is a nice overview on proof techniques, all with a common example, from Estie Arkin available [here].
  • • The 4th, full, seminar (Sem3) will take place Nov 5, 13:00-17:30, in SP6225.
  • • The 5th, full, seminar (Sem4) will take place Nov 28, 09:00-13:00, in SP7226.
  • • The 6th, full, seminar (Sem5) will take place Dec 19, 09:00-13:00, in SP5226.
  • • The 7th, full, seminar (Sem6) will take place May 9, 13:00-17:30, in SP7226.

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