3.415-Approximation for Coflow Scheduling via Iterated Rounding
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909517264977920 |
|---|---|
| author | Rohwedder, Lars Schnaars, Leander |
| author_facet | Rohwedder, Lars Schnaars, Leander |
| contents | We provide an algorithm giving a $\frac{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 $\mathbb{P}\neq\mathbb{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_21197 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | 3.415-Approximation for Coflow Scheduling via Iterated Rounding Rohwedder, Lars Schnaars, Leander Data Structures and Algorithms Optimization and Control We provide an algorithm giving a $\frac{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 $\mathbb{P}\neq\mathbb{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. |
| title | 3.415-Approximation for Coflow Scheduling via Iterated Rounding |
| topic | Data Structures and Algorithms Optimization and Control |
| url | https://arxiv.org/abs/2502.21197 |