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