Treffer: SCHEDULING TO MINIMIZE TOTAL WEIGHTED COMPLETION TIME VIA TIME-INDEXED LINEAR PROGRAMMING RELAXATIONS.

We study approximation algorithms for problems of scheduling precedence constrained jobs with the objective of minimizing total weighted completion time, in identical and related machine models. We give algorithms that improve upon many previous 15- to 20-year-old state-of-the-art results. A major theme in these results is the use of time-indexed linear programming relaxations, which are quite natural for their respective problems. We also consider the scheduling problem of minimizing total weighted completion time on unrelated machines. The recent breakthrough result of [N. Bansal, A. Srinivasan, and O. Svensson, in Proceedings of the 48th Annual ACM Symposium on Theory of Computing, ACM, 2016, pp. 156-167] gave a (1.5 c)-approximation for the problem, based on a two-round lift-and-project of the SDP relaxation for the problem. Our main result is that a (1.5 c)-approximation can also be achieved using a natural and considerably simpler time-indexed linear programming relaxation for the problem. We hope this relaxation can provide new insights into the problem. [ABSTRACT FROM AUTHOR]

Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)