# 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

### Ninth tutorial class - 2022/04/25

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.

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.

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