Strong LP Formulations and Primal-Dual Approximation Algorithms
David Shmoys
School of Operations Research and Information Engineering
Cornell University
Wednesday, January 19, 2011
4:30 - 5:30 PM
Y2E2 101
Abstract:
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,
the capacitated lot-sizing problem, and a location-routing problem that
arose recently in the context of determining bases for aircraft serving
medical patients (for the province of Ontario). For the last of these,
we will also discuss the motivating application in more detail, along with
a ``daily planning'' version of this problem that can be addressed via
integer programming methods.
This is joint work with Tim Carnes.
Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html