Brief announcement: Improved approximation algorithms for scheduling co-flows

Samir Khuller; Manish Purohit

doi:10.1145/2935764.2935809

Brief announcement: Improved approximation algorithms for scheduling co-flows

Samir Khuller, Manish Purohit

Computer Science

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

25 Scopus citations

Abstract

Co-flow scheduling is a recent networking abstraction introduced to capture application-level communication patterns in datacenters. In this paper, we consider the offline co-flow scheduling problem with release times to minimize the total weighted completion time. Recently, Qiu, Stein and Zhong [1] obtained the first constant approximation algorithms for this problem with a deterministic 67/3-approximation and a randomized (9 + 16√2/3) ≈ 16.54-approximation. In this paper, we improve upon their algorithm to yield a deterministic 12-approximation algorithm. For the special case when all release times are zero, we obtain a deterministic 8-approximation and a randomized (3 + 2√2) ≈ 5.83-approximation.

Original language	English (US)
Title of host publication	SPAA 2016 - Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures
Publisher	Association for Computing Machinery
Pages	239-240
Number of pages	2
ISBN (Electronic)	9781450342100
DOIs	https://doi.org/10.1145/2935764.2935809
State	Published - Jul 11 2016
Event	28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016 - Pacific Grove, United States Duration: Jul 11 2016 → Jul 13 2016

Publication series

Name	Annual ACM Symposium on Parallelism in Algorithms and Architectures
Volume	11-13-July-2016

Conference

Conference	28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016
Country/Territory	United States
City	Pacific Grove
Period	7/11/16 → 7/13/16

ASJC Scopus subject areas

Software
Theoretical Computer Science
Hardware and Architecture

Access to Document

10.1145/2935764.2935809

Cite this

Khuller, S., & Purohit, M. (2016). Brief announcement: Improved approximation algorithms for scheduling co-flows. In SPAA 2016 - Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (pp. 239-240). (Annual ACM Symposium on Parallelism in Algorithms and Architectures; Vol. 11-13-July-2016). Association for Computing Machinery. https://doi.org/10.1145/2935764.2935809

@inproceedings{578a5ab1d0594ac4bcc9d10342d338c4,

title = "Brief announcement: Improved approximation algorithms for scheduling co-flows",

abstract = "Co-flow scheduling is a recent networking abstraction introduced to capture application-level communication patterns in datacenters. In this paper, we consider the offline co-flow scheduling problem with release times to minimize the total weighted completion time. Recently, Qiu, Stein and Zhong [1] obtained the first constant approximation algorithms for this problem with a deterministic 67/3-approximation and a randomized (9 + 16√2/3) ≈ 16.54-approximation. In this paper, we improve upon their algorithm to yield a deterministic 12-approximation algorithm. For the special case when all release times are zero, we obtain a deterministic 8-approximation and a randomized (3 + 2√2) ≈ 5.83-approximation.",

author = "Samir Khuller and Manish Purohit",

note = "Funding Information: This work is supported by NSF grant CCF 1217890.; 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016 ; Conference date: 11-07-2016 Through 13-07-2016",

year = "2016",

month = jul,

day = "11",

doi = "10.1145/2935764.2935809",

language = "English (US)",

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

publisher = "Association for Computing Machinery",

pages = "239--240",

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

}

Khuller, S & Purohit, M 2016, Brief announcement: Improved approximation algorithms for scheduling co-flows. in SPAA 2016 - Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures. Annual ACM Symposium on Parallelism in Algorithms and Architectures, vol. 11-13-July-2016, Association for Computing Machinery, pp. 239-240, 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016, Pacific Grove, United States, 7/11/16. https://doi.org/10.1145/2935764.2935809

Brief announcement: Improved approximation algorithms for scheduling co-flows. / Khuller, Samir; Purohit, Manish.
SPAA 2016 - Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery, 2016. p. 239-240 (Annual ACM Symposium on Parallelism in Algorithms and Architectures; Vol. 11-13-July-2016).

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

TY - GEN

T1 - Brief announcement

T2 - 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016

AU - Khuller, Samir

AU - Purohit, Manish

N1 - Funding Information: This work is supported by NSF grant CCF 1217890.

PY - 2016/7/11

Y1 - 2016/7/11

N2 - Co-flow scheduling is a recent networking abstraction introduced to capture application-level communication patterns in datacenters. In this paper, we consider the offline co-flow scheduling problem with release times to minimize the total weighted completion time. Recently, Qiu, Stein and Zhong [1] obtained the first constant approximation algorithms for this problem with a deterministic 67/3-approximation and a randomized (9 + 16√2/3) ≈ 16.54-approximation. In this paper, we improve upon their algorithm to yield a deterministic 12-approximation algorithm. For the special case when all release times are zero, we obtain a deterministic 8-approximation and a randomized (3 + 2√2) ≈ 5.83-approximation.

AB - Co-flow scheduling is a recent networking abstraction introduced to capture application-level communication patterns in datacenters. In this paper, we consider the offline co-flow scheduling problem with release times to minimize the total weighted completion time. Recently, Qiu, Stein and Zhong [1] obtained the first constant approximation algorithms for this problem with a deterministic 67/3-approximation and a randomized (9 + 16√2/3) ≈ 16.54-approximation. In this paper, we improve upon their algorithm to yield a deterministic 12-approximation algorithm. For the special case when all release times are zero, we obtain a deterministic 8-approximation and a randomized (3 + 2√2) ≈ 5.83-approximation.

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

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

U2 - 10.1145/2935764.2935809

DO - 10.1145/2935764.2935809

M3 - Conference contribution

AN - SCOPUS:84979730158

T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures

SP - 239

EP - 240

BT - SPAA 2016 - Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures

PB - Association for Computing Machinery

Y2 - 11 July 2016 through 13 July 2016

ER -

Brief announcement: Improved approximation algorithms for scheduling co-flows

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this