[2211.10398] Improved Approximations for Unrelated Machine Scheduling
source link: https://arxiv.org/abs/2211.10398
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[Submitted on 18 Nov 2022]
Improved Approximations for Unrelated Machine Scheduling
We revisit two well-studied scheduling problems in the unrelated machines setting where each job can have a different processing time on each machine. For minimizing total weighted completion time we give a 1.45-approximation, which improves upon the previous 1.488-approximation [Im and Shadloo SODA 2020]. The key technical ingredient in this improvement lies in a new rounding scheme that gives strong negative correlation with less restrictions. For minimizing $L_k$-norms of machine loads, inspired by [Kalaitzis et al. SODA 2017], we give better approximation algorithms. In particular we give a $\sqrt {4/3}$-approximation for the $L_2$-norm which improves upon the former $\sqrt 2$-approximations due to [Azar-Epstein STOC 2005] and [Kumar et al. JACM 2009].
| Comments: | To appear in SODA 2023 |
| Subjects: | Data Structures and Algorithms (cs.DS) |
| Cite as: | arXiv:2211.10398 [cs.DS] |
| (or arXiv:2211.10398v1 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2211.10398 |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK