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

Saurabh Kumar, Samir Khuller

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

1 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
CountryAustria
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

    Kumar, S., & Khuller, S. (2018). Brief announcement: A greedy 2 approximation for the active time problem. In SPAA 2018 - Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (pp. 347-349). (Annual ACM Symposium on Parallelism in Algorithms and Architectures). Association for Computing Machinery. https://doi.org/10.1145/3210377.3210659