PREREQUISITES:

Attendees are expected to be familiar with elementary notions of linear algebra, probability theory and, possibly, complexity theory and linear programming. However, all the needed definitions and lemmas will be recalled during the seminars.

ABSTRACT:

IIterative Rounding is a recent, and very powerful tool to design

approximation algorithms. The basic idea is as follows. One solves a

(carefully chosen) linear programming relaxation of the considered

NP-hard problem. Then one rounds some variable in the fractional

solution (which corresponds to fixing part of the solution under

construction) according to proper rounding rules. The problem is then

simplified, and the process is iterated on the residual problem until

a solution to the original problem is obtained. Alternatively or in

combination to rounding, one can also relax (i.e. drop) one

constraint. This leads to "slightly" infeasible solutions. In these

seminars we will describe a representative sample of the most relevant

results obtained via iterative rounding in the literature.

The seminars will be tentatively organized as follows. In the first

week, we will introduce approximation algorithms, and present a few

foundamental results and techniques in the area. The second week will

be devoted to approximation algorithms based on linear programming. We

will first introduce linear programming, and then present some

LP-based techniques in approximation algorithms. The final part of the

week will be devoted to iterative rounding.

Sala Seminari W

April 8-12 and May 6-10

Mon: 16 - 18

Tue, Wed, Thu, Fri: 9 - 11