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

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.