Graph Scheduling with Group Completion Times

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 and it completes when the last edge has been scheduled.

Two popular variants of this problem are Coflow Scheduling and Data Migration.

Our main result is extending 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+\epsilon)$-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 + \phi)$-approximation that improves when OPT is small.

Taking the best of this and our main result, we obtain an improvement of the approximation rate for Data Migration in any regime.