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