Benutzer: Gast  Login
Titel:

3.415-Approximation for Coflow Scheduling via Iterated Rounding

Dokumenttyp:
Zeitschriftenaufsatz
Autor(en):
Rohwedder, Lars; Schnaars, Leander
Nicht-TUM Koautoren:
ja
Kooperation:
international
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 [Aga+18], Fukunaga [Fuk22], and others. We additionally show that in an asymptotic setting, the algorithm achieves a (2+ϵ)-approximation, which is essentially optimal under P≠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.
Stichworte:
adone
Intellectual Contribution:
Discipline-based Research
Zeitschriftentitel:
CoRR
Journal gelistet in FT50 Ranking:
nein
Jahr:
2025
Jahr / Monat:
2025-02
Volltext / DOI:
doi:10.48550/ARXIV.2502.21197
Verlag / Institution:
arXiv
Publikationsdatum:
28.02.2025
Urteilsbesprechung:
None
Key publication:
Ja
Peer reviewed:
Nein
commissioned:
not commissioned
Technology:
Nein
Interdisziplinarität:
Nein
Leitbild:
;
Ethics und Sustainability:
Nein
SDG:
;
 BibTeX