Approximation and Online Algorithms: Tutorial

Welcome to the website to the tutorial class of Approximation and Online Algorithms (lecturer Jiří Sgall). We are scheduled on Tuesday, 09:00 in room S1.

If you have a feeling that

write me an email (tung@iuuk.mff.cuni.cz) before it's too late. We'll meet (in cyberspace if needed) and try to resolve it somehow.

How to obtain credit?

You will get credit for solving homework. There should be 12 exercises. You need 66 % of the points to obtain the credit.

Submit homework using the postal owl (link to our course). The enrollment token to our course is 2d18c7763462.

I encourage discussing homework solutions among yourselves. However, make sure you create the submitted solution on your own.

Tutorial content

  1. : Hardness of approximation.
  2. : Metric spaces.
  3. : k-server and its connection to caching.
  4. : Online bipartite matching: deterministic algorithm, deterministic lower bound, lower bound on naive randomized algorithm.
  5. : Deterministic & randomized algorithms for cow path.
  6. : Separation problem for SDP, approximation algorithm for MAX2SAT via SDP (notes in preparation).
  7. : Class cancelled due to health reasons.
  8. : The hows of semidefinite programming.
  9. : Approximation algorithm for Feedback Vertex Set via primal-dual programming (Section 7.2 in the book). Integrality gap (Section 5.6 in the book) for Steiner Tree (and thus for Steiner Forest) (Section 5.7 in the book, look at the picture).
  10. : Primal-dual algorithm for Set Cover/Hitting Set (Section 7.1 in the book).
  11. : Linear programming crash-course.
  12. : We re-invented an FPTAS for Knapsack (Section 3.1 in the book).
  13. : We talked about approximation algorithms for Metric TSP (Section 2.4 in the book) and Scheduling on Uniform Machines (Section 2.3 in the book).