{"ID":5438831,"CreatedAt":"2026-07-01T01:17:58.482524686Z","UpdatedAt":"2026-07-03T11:37:34.911515878Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.31530","arxiv_id":"2606.31530","title":"Graph Scheduling with Group Completion Times","abstract":"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+ε)$-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 + φ)$-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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2606.31530","url_pdf":"https://arxiv.org/pdf/2606.31530v1","authors":"[\"Lars Rohwedder\",\"Leander Schnaars\"]","published":"2026-06-30T11:44:19Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.OC\"]","methods":"[]","has_code":false}