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 Tuesday, 09:00 in room S1.
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 an email (tung@iuuk.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 12 exercises.
You need 66 % of the points to obtain the credit.
Submit homework using the postal owl (link to our course).
The enrollment token to our course is 2d18c7763462.
I encourage discussing homework solutions among yourselves.
However, make sure you create the submitted solution on your own.
Tutorial content
-
:
Separation problem for SDP, approximation algorithm for MAX2SAT via SDP (notes in preparation).
-
:
Class cancelled due to health reasons.
-
:
The hows of semidefinite programming.
-
: Approximation algorithm for Feedback Vertex Set via primal-dual programming (Section 7.2 in the book). Integrality gap (Section 5.6 in the book) for Steiner Tree (and thus for Steiner Forest) (Section 5.7 in the book, look at the picture).
-
: Primal-dual algorithm for Set Cover/Hitting Set (Section 7.1 in the book).
-
: Linear programming crash-course.
-
: We re-invented an FPTAS for Knapsack (Section 3.1 in the book).
-
: We talked about approximation algorithms for Metric TSP (Section 2.4 in the book) and Scheduling on Uniform Machines (Section 2.3 in the book).