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 Monday, 14:00 in room S8.
If you have a feeling that
write me (email@example.com) before it's too late.
We'll meet (in cyberspace if needed) and try to resolve it somehow.
- you don't understand something,
- you can't make a deadline,
- you don't have enough points for the credit,
- you don't know something you are supposed to know,
- I haven't told you something you are supposed to know,
- I should change or improve something,
- for some reason you are not able to obtain a perfect grade from this course
How to obtain credit?
You will get credit for solving homework.
There should be 3 homework sets.
You need 66 % of the points to obtain the credit.
The final requirement is strictly more than 70 points.
Submit your homework solutions in the Postal Owl.
The enrollment token is
I encourage discussing homework solutions among yourselves.
However, make sure you create the submitted solution on your own.
Eleventh tutorial class -
Hardness of approximation.
Tenth tutorial class -
Online bipartite matching and probabilistically checkable proofs.
Ninth tutorial class -
Paging and its relation to k-Server.
This (and the following) class(es) are going to be taught by Jiří Sgall as I am injured.
Eighth tutorial class -
Basic online algorithms: Cow-Path and Ski Rental problems.
Seventh tutorial class -
Sixth tutorial class -
The hows of semidefinite programming.
Fifth tutorial class -
Approximating MAX2SAT using semidefinite programming.
See the textbook by Vazirani for details.
Fourth tutorial class -
Integrality gap for the LP from the lecture for Steiner forest.
A primal-dual algorithm for Feedback Vertex Set.
Third tutorial class -
A primal-dual algorithm for Hitting Set.
The shortest path algorithm on the lecture is in fact Dijkstra's algorithm.
Second tutorial class -
Linear programming crash course. A 2-approximation for Weighted Vertex Cover.
First tutorial class -
The notes are being prepared.
We spoke about an FPTAS for Knapsack.
It is described quite well in the book.