Select and permute: An improved online framework for scheduling to minimize weighted completion time

Samir Khuller, Jingling Li, Pascal Sturmfels, Kevin Sun, Prayaag Venkat*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationLATIN 2018
Subtitle of host publicationTheoretical Informatics - 13th Latin American Symposium, Proceedings
EditorsMiguel A. Mosteiro, Michael A. Bender, Martin Farach-Colton
PublisherSpringer Verlag
Pages669-682
Number of pages14
ISBN (Print)9783319774039
DOIs
StatePublished - Jan 1 2018
Event13th International Symposium on Latin American Theoretical Informatics, LATIN 2018 - Buenos Aires, Argentina
Duration: Apr 16 2018Apr 19 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10807 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th International Symposium on Latin American Theoretical Informatics, LATIN 2018
CountryArgentina
CityBuenos Aires
Period4/16/184/19/18

Keywords

  • Coflow scheduling
  • Concurrent clusters
  • Concurrent open shop
  • Online algorithms

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Select and permute: An improved online framework for scheduling to minimize weighted completion time'. Together they form a unique fingerprint.

  • Cite this

    Khuller, S., Li, J., Sturmfels, P., Sun, K., & Venkat, P. (2018). Select and permute: An improved online framework for scheduling to minimize weighted completion time. In M. A. Mosteiro, M. A. Bender, & M. Farach-Colton (Eds.), LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Proceedings (pp. 669-682). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10807 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-77404-6_49