Polytope Scheduling with Groups: Unified Models and Optimal Guarantees
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914320269443072 |
|---|---|
| author | Lindermayr, Alexander Liu, Zhenwei Megow, Nicole |
| author_facet | Lindermayr, Alexander Liu, Zhenwei Megow, Nicole |
| contents | We propose new abstract and unified perspectives on a range of scheduling and graph coloring problems with general min-sum objectives. Specifically, we consider various problems where the objective function is the weighted sum of completion times over groups of entities (jobs, vertices, or edges), thereby generalizing two important objectives in scheduling: makespan and the sum of weighted completion times.
As one of our main results, we present a best-possible $\mathcal O(\log g)$-competitive algorithm in the non-clairvoyant online setting, where $g$ denotes the size of the largest group. This is the first non-trivial competitive bound for several problems with group completion time objective, and it is an exponential improvement over previous results for non-clairvoyant coflow scheduling. For offline scheduling, we provide elegant yet powerful meta-frameworks that, in a unifying way, yield new or stronger approximation algorithms for our new abstract problems as well as for previously well-studied special cases. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_17682 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Polytope Scheduling with Groups: Unified Models and Optimal Guarantees Lindermayr, Alexander Liu, Zhenwei Megow, Nicole Data Structures and Algorithms F.2.2 We propose new abstract and unified perspectives on a range of scheduling and graph coloring problems with general min-sum objectives. Specifically, we consider various problems where the objective function is the weighted sum of completion times over groups of entities (jobs, vertices, or edges), thereby generalizing two important objectives in scheduling: makespan and the sum of weighted completion times. As one of our main results, we present a best-possible $\mathcal O(\log g)$-competitive algorithm in the non-clairvoyant online setting, where $g$ denotes the size of the largest group. This is the first non-trivial competitive bound for several problems with group completion time objective, and it is an exponential improvement over previous results for non-clairvoyant coflow scheduling. For offline scheduling, we provide elegant yet powerful meta-frameworks that, in a unifying way, yield new or stronger approximation algorithms for our new abstract problems as well as for previously well-studied special cases. |
| title | Polytope Scheduling with Groups: Unified Models and Optimal Guarantees |
| topic | Data Structures and Algorithms F.2.2 |
| url | https://arxiv.org/abs/2501.17682 |