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 ( 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 -

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. Solutions.

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.