Scheduling with Communication Delays via LP Hierarchies and Clustering II: Weighted Completion Times on Related Machines
Lists
Only you see this
Abstract
We consider the problem of scheduling jobs with precedence constraints on related machines to minimize the weighted sum of completion times, in the presence of communication delays. In this setting, denoted by Q | prec, c | ΣwjCj, if two dependent jobs are scheduled on different machines, then at least c units of communication delay time must pass between their executions. Our main result is an O(log4 n)-approximation algorithm for the problem. As a byproduct of our result, we also obtain an O(log3 n)-approximation algorithm for the problem of minimizing makespan Q | prec, c | Cmax, which improves upon the O(log5 n/ log log n)-approximation algorithm due to a recent work of Maiti et al. [MRS+20].
BibTeX
@inproceedings{davies2021scheduling,
author = {Sami Davies and Janardhan Kulkarni and Thomas Rothvoss and Jakub Tarnawski and Yihao Zhang},
title = {{Scheduling with Communication Delays via LP Hierarchies and Clustering II: Weighted Completion Times on Related Machines}},
booktitle = {SODA},
year = {2021},
doi = {10.1137/1.9781611976465.176},
}Loading related content...