Can I read Improved Approximation Coflows Scheduling Algorithms for Minimizing the Total Weighted Completion Time and Makespan in Heterogeneous Parallel Networks on EtoBox?

Improved Approximation Coflows Scheduling Algorithms for Minimizing the Total Weighted Completion Time and Makespan in Heterogeneous Parallel Networks by Chen, Chi-Yeh is a scholarly article available to read on EtoBox.

What is Improved Approximation Coflows Scheduling Algorithms for Minimizing the Total Weighted Completion Time and Makespan in Heterogeneous Parallel Networks about?

Coflow is a network abstraction used to represent communication patterns in data centers. The coflow scheduling problem encountered in large data centers is a challenging $\mathcal{NP}$-hard problem. This paper tackles the scheduling problem of coflows with release times in heterogeneous parallel networks, which feature an architecture consisting of multiple network cores running in parallel. Two polynomial-time approximation algorithms are presented in this paper, designed to minimize the total weighted completion time and makespan in heterogeneous parallel networks, respectively. For any given $\epsilon>0$, our proposed approximation algorithm for minimizing the total weighted completion time achieves approximation ratios of $3 + \epsilon$ and $2 + \epsilon$ in the cases of arbitrary and zero release times, respectively. Additionally, we introduce an approximation algorithm for minimizing the makespan, achieving an approximation ratio of $2 + \epsilon$ for $\epsilon>0$. Notably, these advancements surpass the previously best-known approximation ratio of $O(\log m/ \log \log m)$ for both minimizing the total weighted completion time and makespan. This result also improves upon the

Author

Chen, Chi-Yeh

Published

2023

Language

EN