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

Saurabh Kumar; Samir Khuller

doi:10.1145/3210377.3210659

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

Saurabh Kumar, Samir Khuller

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

6 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 language	English (US)
Title of host publication	SPAA 2018 - Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures
Publisher	Association for Computing Machinery
Pages	347-349
Number of pages	3
ISBN (Electronic)	9781450357999
DOIs	https://doi.org/10.1145/3210377.3210659
State	Published - Jul 11 2018
Event	30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018 - Vienna, Austria Duration: Jul 16 2018 → Jul 18 2018

Publication series

Name	Annual ACM Symposium on Parallelism in Algorithms and Architectures

Conference

Conference	30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018
Country/Territory	Austria
City	Vienna
Period	7/16/18 → 7/18/18

Funding

\u2217This work is based on the master\u2019s thesis of Kumar supervised by Khuller \u2020Supported by NSF Award CNS 1560193

Keywords

Scheduling Algorithms

ASJC Scopus subject areas

Software
Theoretical Computer Science
Hardware and Architecture

Access to Document

10.1145/3210377.3210659

Cite this

@inproceedings{3542511106c443ac9c85a4044d2a7ebb,

title = "Brief announcement: A greedy 2 approximation for the active time problem",

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.",

keywords = "Scheduling Algorithms",

author = "Saurabh Kumar and Samir Khuller",

note = "Publisher Copyright: {\textcopyright} 2018 Copyright held by the owner/author(s).; 30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018 ; Conference date: 16-07-2018 Through 18-07-2018",

year = "2018",

month = jul,

day = "11",

doi = "10.1145/3210377.3210659",

language = "English (US)",

series = "Annual ACM Symposium on Parallelism in Algorithms and Architectures",

publisher = "Association for Computing Machinery",

pages = "347--349",

booktitle = "SPAA 2018 - Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures",

}

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. Annual ACM Symposium on Parallelism in Algorithms and Architectures, Association for Computing Machinery, pp. 347-349, 30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018, Vienna, Austria, 7/16/18. https://doi.org/10.1145/3210377.3210659

Brief announcement: A greedy 2 approximation for the active time problem. / Kumar, Saurabh; Khuller, Samir.
SPAA 2018 - Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery, 2018. p. 347-349 (Annual ACM Symposium on Parallelism in Algorithms and Architectures).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Brief announcement

T2 - 30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2018

AU - Kumar, Saurabh

AU - Khuller, Samir

PY - 2018/7/11

Y1 - 2018/7/11

N2 - 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.

AB - 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.

KW - Scheduling Algorithms

UR - http://www.scopus.com/inward/record.url?scp=85053484812&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85053484812&partnerID=8YFLogxK

U2 - 10.1145/3210377.3210659

DO - 10.1145/3210377.3210659

M3 - Conference contribution

AN - SCOPUS:85053484812

T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures

SP - 347

EP - 349

BT - SPAA 2018 - Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures

PB - Association for Computing Machinery

Y2 - 16 July 2018 through 18 July 2018

ER -

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

Abstract

Publication series

Conference

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this