3.415-Approximation for Coflow Scheduling via Iterated Rounding

Abstract

We provide an algorithm giving a $\frac{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+\hat{I}\mu$)-approximation, which is essentially optimal under $\mathbb{P}\ne \mathbb{NP}$. 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.

27 pages, 1 figure