Article ID: | iaor20003427 |
Country: | Netherlands |
Volume: | 98 |
Issue: | 1/2 |
Start Page Number: | 29 |
End Page Number: | 38 |
Publication Date: | Nov 1999 |
Journal: | Discrete Applied Mathematics |
Authors: | Motwani Rajeev, Chekuri Chandra |
Keywords: | programming: linear |
We consider the problem of scheduling a set of jobs on a single machine with the objective of minimizing sum of weighted completion times. The problem is NP-hard when there are precedence constraints between jobs. We provide an efficient combinatorial 2-approximation algorithm for this problem. In contrast to our work, earlier approximation algorithms achieving constant factor approximations are based on solving a linear programming relaxation of the problem. We also show that the linear ordering relaxation of Potts has an integrality gap of 2.