@inproceedings{dda466834969448aae4df2577f36f728,
title = "Select and permute: An improved online framework for scheduling to minimize weighted completion time",
abstract = "In this paper, we introduce a new online scheduling framework for minimizing total weighted completion time in a general setting. The framework is inspired by the work of Hall et al. [10] and Garg et al. [8], who show how to convert an offline approximation to an online scheme. Our framework uses two offline approximation algorithms—one for the simpler problem of scheduling without release times, and another for the minimum unscheduled weight problem—to create an online algorithm with provably good competitive ratios. We illustrate multiple applications of this method that yield improved competitive ratios. Our framework gives algorithms with the best or only-known competitive ratios for the concurrent open shop, coflow, and concurrent cluster models. We also introduce a randomized variant of our framework based on the ideas of Chakrabarti et al. [3] and use it to achieve improved competitive ratios for these same problems.",
keywords = "Coflow scheduling, Concurrent clusters, Concurrent open shop, Online algorithms",
author = "Samir Khuller and Jingling Li and Pascal Sturmfels and Kevin Sun and Prayaag Venkat",
note = "Funding Information: We would like to thank Sungjin Im and Clifford Stein for directing us to [3, 17], and William Gasarch for organizing the REU program. All authors performed this work at the University of Maryland, College Park, under the support of NSF REU Grant CNS 156019. We would also like to thank An Zhu and Google for their support, and the LILAC program at Bryn Mawr College Funding Information: All authors performed this work at the University of Maryland, College Park, under the support of NSF REU Grant CNS 156019. We would also like to thank An Zhu and Google for their support, and the LILAC program at Bryn Mawr College. Publisher Copyright: {\textcopyright} Springer International Publishing AG, part of Springer Nature 2018.; 13th International Symposium on Latin American Theoretical Informatics, LATIN 2018 ; Conference date: 16-04-2018 Through 19-04-2018",
year = "2018",
doi = "10.1007/978-3-319-77404-6_49",
language = "English (US)",
isbn = "9783319774039",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "669--682",
editor = "Mosteiro, {Miguel A.} and Bender, {Michael A.} and Martin Farach-Colton",
booktitle = "LATIN 2018",
}