Seminario Interdipartimentale di Algoritmica  

Monday, March 21, 2005, 12:00 noon
Improved approximation schemes for linear programming relaxations of combinatorial optimization problems
Fabian Chudak
ETH Zurich

DI - Department of Computer Science
Seminar Room, third floor

Abstract:

We consider a generic paradigm to design improved approximation schemes for linear programming relaxations of combinatorial optimization problems. For the case of the uncapacitated facility location problem, the scheduling problem R || Cmax and the set covering problem we substantially improve the running time dependence on e from the previously known O(1/e^2) to O(1/e). For the survivable network design problem we improve the dependence from O(1/e^2) to O((1/e) log(1/e)). We present some preliminary computational results that seem to suggest that our algorithms may prove very competitive in practice. Our results build mainly on work of Nesterov and extend the work of Bienstock and Iyengar. This talk will be primarily based on the uncapacitated facility location problem and assumes no previous knowledge of the subject.