{"id":"arxiv/2606.31530","url":"https://arxiv.org/abs/2606.31530","tags":["cs.DS","math.OC"],"score":0,"title":"Graph Scheduling with Group Completion Times","domain":"cs.DS","source":"arxiv","authors":["Lars Rohwedder","Leander Schnaars"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-30","reactions":{}}