Fall 2010 Seminar Series

DATE: December 9th
LOCATION: E51-145
TIME: 4:15pm
Reception immediately following in same room

SPEAKER:
David B. Shmoys

TITLE
Strong LP Formulations and Primal-Dual Approximation Algorithms

ABSTRACT
One of the primary engines behind the tremendous advances in integer programming as a computational tool over the past decades has been the understanding of increasingly stronger formulations to obtain improved bounds. In contrast, there has not been as much work in providing a theoretical basis for these strengthened LP relaxations, in spite of significant advances in the design and analysis of approximation algorithms over this period. We will present a variety of settings in which additional combinatorially-defined valid inequalities can yield improved performance guarantees in the context of the design and analysis of primal-dual approximation algorithms. We will present several 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 well as the capacitated lot-sizing problem, some single-machine scheduling problems, and a location-routing problem that arose recently in the context of determining bases for aircraft serving medical patients. We will also discuss empirical implications for some of these theoretically-motivated algorithms.

 

This is joint work with Tim Carnes and Maurice Cheung.