Approximation Algorithms

Exam

Test results are in the file below (additional link here). Tonight I will extend it by all other results.

New version of the file with results is available. It shows lower bounds for your grades.

Grades

Sum of points (from exam and exercises):

6 => 5.0

5 => 4.5

4 => 4.0

3 => 3.5

2 => 3.0

Sum of points in the Lab (possible to get from 0 to 3 with fractions):

1 => 3.0

2 => 4.0

3 => 5.0

The final grade = 70% * exam/exercises grade + 30% * lab grade

Literature

1. "Approximation Algorithms" by Vijay Vazirani

2. The book is divided in three parts - during the lecture I will try to follow approximately (pun intended) the first half of each part.

3. "Probability and Computing" by Michael Mitzenmacher and Eli Upfal (for lab 3)

Exercises

• 1. Exercises 1-6 from Chapter 1

  2. Exercises 1-6 from Chapter 2

  3. Exercises 1-6 from Chapter 3

  4. Exercises 1-3 and 8 from Chapter 12

  5. Exercises 1-4 from Chapter 13

1. Exercises 1-5 from Chapter 14

2. Exercises 3-6 from Chapter 4

3. Exercises 1-3 from Chapter 5

Lab

The following deadlines are for sending your source codes, discussion on them should take place approximately within a week from sending (before or after) during labs or office hours. You are allowed to program the tasks in groups of 2-3 people.

• 1. Deadline: 1st of April 2016. Program an approximation algorithm for metric Traveling Salesperson Problem. Your mini-project should include some basic tests for your program.

     1. A simpler version: 2-approximation (for this version you may get up to 0.666 point)

     2. A more complex version: 1.5-approximation (for this version you may get up to 1.0 point)

  2. Deadline: 6th of May 2016. Write a program which for a linear primal program (given in any form suitable for you) produces its dual.

• • 1. A simpler version (0.666 point): assume that input is given in the standarized form

    2. For the full version(1.0 point): first adapt input so that all variables are non-negative and that only one type of inequalities appear in the input.

• 3. Deadline: 10th of June (meeting rather before than after!). Write a program tha approximates MAX-SAT, i.e. finds values for boolean variables that satisfy the maximum number of clauses.

• • 1. A simpler version (0.666 point): a randomized algorithm where the expected value counts as result

• 4. Derandomization of the above

  5. Both: be prepared to talk also about MAX-CUT - randomized version in the first case and its derandomization in the second