Brief announcement: A greedy 2 approximation for the active time problem

Saurabh Kumar, Samir Khuller

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

4 Scopus citations

Abstract

In this note, we give a simple 2 approximation for the active time problem - we are given a set of pre-emptible jobs, each with an integral release time, deadline and required processing length. The jobs need to be scheduled on a machine that can process at most д distinct job units at any given integral time slot, in such a way that we minimize the time the machine is on i.e the active time. Our algorithm matches the state of the art bound obtained by a significantly more involved LP rounding scheme.

Original languageEnglish (US)
Title of host publicationSPAA 2018 - Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures
PublisherAssociation for Computing Machinery
Pages347-349
Number of pages3
ISBN (Electronic)9781450357999
DOIs
StatePublished - Jul 11 2018
Event30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018 - Vienna, Austria
Duration: Jul 16 2018Jul 18 2018

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures

Conference

Conference30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018
Country/TerritoryAustria
CityVienna
Period7/16/187/18/18

Keywords

  • Scheduling Algorithms

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Brief announcement: A greedy 2 approximation for the active time problem'. Together they form a unique fingerprint.

Cite this