User: Guest  Login
Title:

3.415-Approximation for Coflow Scheduling via Iterated Rounding

Document type:
Zeitschriftenaufsatz
Author(s):
Rohwedder, Lars; Schnaars, Leander
Non-TUM Co-author(s):
ja
Cooperation:
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.
Keywords:
adone
Intellectual Contribution:
Discipline-based Research
Journal title:
CoRR
Journal listet in FT50 ranking:
nein
Year:
2025
Year / month:
2025-02
Fulltext / DOI:
doi:10.48550/ARXIV.2502.21197
Publisher:
arXiv
Date of publication:
28.02.2025
Judgement review:
None
Key publication:
Ja
Peer reviewed:
Nein
Commissioned:
not commissioned
Technology:
Nein
Interdisciplinarity:
Nein
Mission statement:
;
Ethics and Sustainability:
Nein
SDG:
;
 BibTeX