Lift and Project Algorithms for Precedence Constrained Scheduling to Minimize Completion Time
Lists
Only you see this
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.
BibTeX
@inproceedings{garg2019lift,
author = {Shashwat Garg and Janardhan Kulkarni and Shi Li},
title = {{Lift and Project Algorithms for Precedence Constrained Scheduling to Minimize Completion Time}},
booktitle = {SODA},
year = {2019},
url = {https://openreview.net/forum?id=R8NaJiLlHOV},
}Loading related content...