Scheduling jobs with varying parallelizability to reduce variance

Anupam Gupta, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Kirk Pruhs

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

Abstract

We give a (2+ε)-speed O(1)-competitive algorithm for scheduling jobs with arbitrary speed-up curves for the ℓ2 norm of flow. We give a similar result for the broadcast setting with varying page sizes.

Original languageEnglish (US)
Title of host publicationSPAA'10 - Proceedings of the 22nd Annual Symposium on Parallelism in Algorithms and Architectures
Pages11-20
Number of pages10
DOIs
StatePublished - 2010
Event22nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'10 - Thira, Santorini, Greece
Duration: Jun 13 2010Jun 15 2010

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures

Conference

Conference22nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'10
Country/TerritoryGreece
CityThira, Santorini
Period6/13/106/15/10

Keywords

  • Online algorithms
  • Scheduling algorithms

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Scheduling jobs with varying parallelizability to reduce variance'. Together they form a unique fingerprint.

Cite this