TY - GEN
T1 - On scheduling coflows
AU - Ahmadi, Saba
AU - Khuller, Samir
AU - Purohit, Manish
AU - Yang, Sheng
N1 - Funding Information:
This work is supported by NSF grant CNS 156019.
PY - 2017
Y1 - 2017
N2 - Applications designed for data-parallel computation frameworks such as MapReduce usually alternate between computation and communication stages. Coflow scheduling is a recent popular networking abstraction introduced to capture such application-level communication patterns in datacenters. In this framework, a datacenter is modeled as a single non-blocking switch with m input ports and m output ports. A coflow j is a collection of flow demands (djio)i∈m,o∈m that is said to be complete once all of its requisite flows have been scheduled. We consider the offline coflow scheduling problem with and without release times to minimize the total weighted completion time. Coflow scheduling generalizes the well studied concurrent open shop scheduling problem and is thus NP-hard. Qiu, Stein and Zhong [15] obtain the first constant approximation algorithms for this problem via LP rounding and give a deterministic673 -approximation and a randomized (9 +16√32) ≈ 16.54-approximation algorithm. In this paper, we give a combinatorial algorithm that yields a deterministic 5-approximation algorithm with release times, and a deterministic 4-approximation for the case without release time.
AB - Applications designed for data-parallel computation frameworks such as MapReduce usually alternate between computation and communication stages. Coflow scheduling is a recent popular networking abstraction introduced to capture such application-level communication patterns in datacenters. In this framework, a datacenter is modeled as a single non-blocking switch with m input ports and m output ports. A coflow j is a collection of flow demands (djio)i∈m,o∈m that is said to be complete once all of its requisite flows have been scheduled. We consider the offline coflow scheduling problem with and without release times to minimize the total weighted completion time. Coflow scheduling generalizes the well studied concurrent open shop scheduling problem and is thus NP-hard. Qiu, Stein and Zhong [15] obtain the first constant approximation algorithms for this problem via LP rounding and give a deterministic673 -approximation and a randomized (9 +16√32) ≈ 16.54-approximation algorithm. In this paper, we give a combinatorial algorithm that yields a deterministic 5-approximation algorithm with release times, and a deterministic 4-approximation for the case without release time.
KW - Coflow scheduling
KW - Concurrent open shop
UR - http://www.scopus.com/inward/record.url?scp=85020535183&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85020535183&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-59250-3_2
DO - 10.1007/978-3-319-59250-3_2
M3 - Conference contribution
AN - SCOPUS:85020535183
SN - 9783319592497
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 13
EP - 24
BT - Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings
A2 - Eisenbrand, Friedrich
A2 - Koenemann, Jochen
PB - Springer Verlag
T2 - 19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017
Y2 - 26 June 2017 through 28 June 2017
ER -