2026-08-25T18:47:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27236 2026-08-25T13:18:19Z ddc:004 open_access

Graph Scheduling with Group Completion Times Rohwedder, Lars Schnaars, Leander Graph Scheduling Approximation Algorithms Iterated Rounding 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lars Rohwedder and Leander Schnaars 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.100 urn:nbn:de:0030-drops-272369 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.100 eng https://creativecommons.org/licenses/by/4.0/legalcode