Distinguished Lecture Series


"Strong LP Formulations and Primal-Dual Approximation Algorithms"

David Shmoys, Cornell University

Thursday, September 23, 2010 at 4:00 P.M.

Room 368 (CIT 3rd floor)

The state of the art of the design and analysis of approximation algorithms for NP-hard discrete optimization has advanced significantly over the past two decades; furthermore, the most prevalent approach has been to rely on the strength of natural linear programming relaxations. Work in computational integer programming over the same time period has shown the power of adding combinatorially-motivated valid inequalities, but this has not been employed often in the design of approximation algorithms. We will show how this approach can be applied in the design and analysis of primal-dual approximation algorithms. We will present several recent approximation results along these lines, starting with a (surprisingly simple) primal-dual analogue of an LP-rounding result of Carr, Fleischer, Leung, & Phillips for the minimum-cost covering knapsack problem, as well as applications to the single-demand facility location problem, the capacitated lot-sizing problem, and a location-routing problem that arose recently in the context of determining bases for aircraft serving medical patients.

This is joint work with Tim Carnes.

Host: Philip Klein

To see the poster for this lecture, please click here.