Tutte seminar - Maurice Cheung

A Primal-Dual Approximation Algorithm for Min-Sum Single Machine Scheduling Problems

Abstract:

We consider the following class of single-machine scheduling problems, where the cost of scheduling each job is a (job-specific) non-decreasing function of its completion time, 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 improve on this result: we give a simple primal-dual algorithm that yields a c-approximation algorithm for any constant c >2. The natural LP relaxation for this problem has unbounded integrality gap. Our algorithm is based on strengthening the LP relaxation by adding a class of valid inequalities known as knapsack-cover inequalities. Furthermore, we generalize this result to allow the machine's speed to vary over time arbitrarily, for which no previous constant-factor approximation algorithm was known. This is joint work with David Shmoys.