Tung Anh Vu
Teaching
Approximation and Online Algorithms, SS 2021/2022
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

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
write me (tung@kam.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 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 `69a5b04fb6a6`

.

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

Tutorial content
Eleventh tutorial class - 2022/05/23
Hardness of approximation.

Tenth tutorial class - 2022/05/09
Online bipartite matching and probabilistically checkable proofs.

Ninth tutorial class - 2022/04/25
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 - 2022/04/11
Basic online algorithms: Cow-Path and Ski Rental problems.
Seventh tutorial class - 2022/04/04
Metrics.
Sixth tutorial class - 2022/03/28
The hows of semidefinite programming.
Solutions.
Fifth tutorial class - 2022/03/21
Approximating MAX2SAT using semidefinite programming.
See the textbook by Vazirani for details.

Fourth tutorial class - 2022/03/14
Integrality gap for the LP from the lecture for Steiner forest.
A primal-dual algorithm for Feedback Vertex Set.
Third tutorial class - 2022/03/07
A primal-dual algorithm for Hitting Set.
The shortest path algorithm on the lecture is in fact Dijkstra's algorithm.
Second tutorial class - 2022/02/28
Linear programming crash course. A 2-approximation for Weighted Vertex Cover.

First tutorial class - 2022/02/21
The notes are being prepared.
We spoke about an FPTAS for Knapsack.
It is described quite well in the book.