In the Graph Scheduling problem, we schedule a given multiset of edges on discrete time steps, such that at each step the set of edges forms a matching. The goal is to minimize the sum of weighted group completion times, where a group is a set of edges that completes when the last edge has been scheduled.
Two popular variants of this problem are Coflow Scheduling and Data Migration. Our main result extends a recent iterated rounding approach from Coflow Scheduling, roughly corresponding to the bipartite case, to the general Graph Scheduling problem. This yields an essentially tight $(2+\varepsilon)$-approximation for the asymptotic setting where OPT is assumed to be large.
For this, we rely on polyhedral techniques from general matching, namely odd-set inequalities, and graph theoretical results on edge colorings in multigraphs. The state-of-the-art approximation algorithm for Data Migration is a $(1 + \varphi)$-approximation that improves when OPT is small. By taking the best of this and our main result, we achieve an improvement in the approximation rate for Data Migration in any regime.
Blogger's Review: This paper successfully enhances the approximation efficiency of the Graph Scheduling problem by extending the iterated rounding method, providing new theoretical support for Data Migration and Coflow Scheduling. It demonstrates the powerful potential of combining graph theory with polyhedral methods, offering new perspectives for optimizing scheduling problems in complex systems.