DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.100

Graph Scheduling with Group Completion Times

Authors: Lars Rohwedder and Leander Schnaars

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

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.

Cite as

Lars Rohwedder and Leander Schnaars. Graph Scheduling with Group Completion Times. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 100:1-100:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{rohwedder_et_al:LIPIcs.ESA.2026.100,
  author =	{Rohwedder, Lars and Schnaars, Leander},
  title =	{{Graph Scheduling with Group Completion Times}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{100:1--100:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.100},
  URN =		{urn:nbn:de:0030-drops-272369},
  doi =		{10.4230/LIPIcs.ESA.2026.100},
  annote =	{Keywords: Graph Scheduling, Approximation Algorithms, Iterated Rounding}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.128

3.415-Approximation for Coflow Scheduling via Iterated Rounding

Authors: Lars Rohwedder and Leander Schnaars

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract

We provide an algorithm giving a 140/41 (< 3.415)-approximation for Coflow Scheduling and a 4.36-approximation for Coflow Scheduling with release dates. This improves upon the best known 4- and respectively 5-approximations and addresses an open question posed by Agarwal, Rajakrishnan, Narayan, Agarwal, Shmoys, and Vahdat [Agarwal et al., 2018], Fukunaga [Fukunaga, 2022], and others. We additionally show that in an asymptotic setting, the algorithm achieves a (2+ε)-approximation, which is essentially optimal under ℙ ≠ NP. The improvements are achieved using a novel edge allocation scheme using iterated LP rounding together with a framework which enables establishing strong bounds for combinations of several edge allocation algorithms.

Cite as

Lars Rohwedder and Leander Schnaars. 3.415-Approximation for Coflow Scheduling via Iterated Rounding. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 128:1-128:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{rohwedder_et_al:LIPIcs.ICALP.2025.128,
  author =	{Rohwedder, Lars and Schnaars, Leander},
  title =	{{3.415-Approximation for Coflow Scheduling via Iterated Rounding}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{128:1--128:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.128},
  URN =		{urn:nbn:de:0030-drops-235050},
  doi =		{10.4230/LIPIcs.ICALP.2025.128},
  annote =	{Keywords: Coflow Scheduling, Approximation Algorithms, Iterated Rounding}
}

Search Results

Documents authored by Schnaars, Leander

Graph Scheduling with Group Completion Times

Abstract

Cite as

3.415-Approximation for Coflow Scheduling via Iterated Rounding

Abstract

Cite as

Thanks for your feedback!

Could not send message