A PRIMAL-DUAL APPROXIMATION ALGORITHM FOR MIN-SUM SINGLE-MACHINE SCHEDULING PROBLEMS

作者：Cheung Maurice^*; Mestre Julian; Shmoys David B; Verschae Jose

来源：SIAM Journal on Discrete Mathematics, 2017, 31(2): 825-838.

DOI：10.1137/16M1086819

• min-sum scheduling
• approximation algorithm
• primal-dual schema
• knapsack cover inequalities

We consider the following single-machine scheduling problem, which is often denoted 1 || Sigma f(j): we are given n jobs to be scheduled on a single machine, where each job j has an integral processing time p(j), and there is a nondecreasing, nonnegative cost function f(j)(C-j)that specifies the cost of finishing j at time C-j; the objective is to minimize Sigma(n)(j=1) f(j)(C-j). Bansal and Pruhs recently gave the first constant approximation algorithm with a performance guarantee of 16. We improve on this result by giving a primal-dual pseudo-polynomial-time algorithm based on the recently introduced knapsack-cover inequalities. The algorithm finds a schedule of cost at most four times the constructed dual solution. Although we show that this bound is tight for our algorithm, we leave open the question of whether the integrality gap of the linear program is less than 4. Finally, we show how the technique can be adapted to yield, for any epsilon > 0, a polynomial time (4 + epsilon)-approximation algorithm for this problem.

• 出版日期2017