3.415-Approximation for Coflow Scheduling via Iterated Rounding

2025/02/28 by Rohwedder, Lars, Schnaars, Leander · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2502.21197

Abstract

We provide an algorithm giving a (140)/(41)(<3.415)-approximation for Coflow Scheduling and a 4.36-approximation for Coflow Scheduling with release dates. This improves upon the best known 4- and respectively 5-approximations and addresses an open question posed by Agarwal, Rajakrishnan, Narayan, Agarwal, Shmoys, and Vahdat [Aga+18], Fukunaga [Fuk22], and others. We additionally show that in an asymptotic setting, the algorithm achieves a (2+ε)-approximation, which is essentially optimal under ℙ≠\mathbbNP. The improvements are achieved using a novel edge allocation scheme using iterated LP rounding together with a framework which enables establishing strong bounds for combinations of several edge allocation algorithms.

Cited by

• Indirect Coflow Scheduling

Related

• Improved Approximation Algorithms for Minimizing the Total Weighted Completion Time of Coflows
• Experimental Analysis of Algorithms for Coflow Scheduling
• Improved Approximation Coflows Scheduling Algorithms for Minimizing the Total Weighted Completion Time and Makespan in Heterogeneous Parallel Networks
• Asymptotically Optimal Approximation Algorithms for Coflow Scheduling
• A Tight Approximation for Co-flow Scheduling for Minimizing Total Weighted Completion Time