Lecturer: Prof. Fabrizio Grandoni

Period: April 8-12,  May 6-10, 2013

 

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:

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

Place: Sala Seminari W

Schedule:

April 8-12  and  May 6-10 
Mon: 16 - 18
Tue, Wed, Thu, Fri: 9 - 11