Paper Info
Title
Lift and Project Algorithms for Precedence Constrained Scheduling to Minimize Completion Time.
Abstract
We consider the classic problem of scheduling jobs with precedence constraints on a set of identical machines to minimize the weighted completion time objective. Understanding the exact approximability of the problem when job lengths are uniform is a well known open problem in scheduling theory. In this paper, we show an optimal algorithm that runs in polynomial time and achieves an approximation factor of (2 + ε) for the weighted completion time objective when the number of machines is a constant. The result is obtained by building on the lift and project approach introduced in a breakthrough work by Levey and Rothvoss [15] for the makespan minimization problem.
Year
DOI
Venue
2019
10.5555/3310435.3310530
SODA '19: Symposium on Discrete Algorithms San Diego California January, 2019
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
0
3
Name
Order
Citations
PageRank
Shashwat Garg1174.87
Janardhan Kulkarni2283.34
Shi Li320822.01