Strong LP Formulations and Primal-Dual Approximation Algorithms

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, which finds a solution of cost at most twice the optimum. We will then consider a broad class of single-machine scheduling problems, where the cost of scheduling each job is a (job-specific) non-decreasing function of the time at which it completes, and the objective is to minimize the total cost of the schedule. Bansal and Pruhs recently gave the first constant approximation algorithm for this setting; we adapt the primal-dual approach to directly yield a 2-approximation algorithm for this class of problems.

This is joint work with Tim Carnes and Maurice Cheung

发言人详细信息

David Shmoys is a Professor of Operations Research and Information Engineering as well as of Computer Science at Cornell University.
He obtained his Ph.D. in Computer Science from the University of California at Berkeley in 1984, and held postdoctoral positions at MSRI in Berkeley and Harvard University, and a faculty position at MIT before joining the Cornell faculty. Shmoys’s research has focused on the design and analysis of efficient algorithms for discrete optimization problems, and his work has highlighted the central role that linear programming plays in the design of approximation algorithms for NP-hard problems. He is a Fellow of the ACM, was an NSF Presidential Young Investigator, and has served on numerous editorial boards, including both the SIAM Journals of Computing and of Discrete Mathematics (for which he was Editor-in-Chief), Mathematics of Operations Research, Operations Research, and Mathematical Programming.

日期：
演讲者：
David Shmoys
所属机构：
Cornell University