Back to Search
Start Over
Approximating weighted completion time via stronger negative correlation.
- Source :
- Journal of Scheduling; Aug2024, Vol. 27 Issue 4, p319-328, 10p
- Publication Year :
- 2024
-
Abstract
- Minimizing the weighted completion time of jobs in the unrelated parallel machines model is a fundamental scheduling problem. The first (3 / 2 - c) –approximation algorithm for this problem, for some constant c > 0 , was obtained in the work of Bansal et al. (SIAM J Comput, 2021). A key ingredient in this work was the first dependent-rounding algorithm with a certain guaranteed amount of negative correlation. We improve upon this guaranteed amount from 1/108 to 1/27, thus also improving upon the constant c in the algorithms of Bansal et al. and Li (SIAM J Comput, 2020) for weighted completion time. Given the now-ubiquitous role played by dependent rounding in scheduling and combinatorial optimization, our improved dependent rounding is also of independent interest. [ABSTRACT FROM AUTHOR]
- Subjects :
- APPROXIMATION algorithms
COMBINATORIAL optimization
SCHEDULING
ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 10946136
- Volume :
- 27
- Issue :
- 4
- Database :
- Complementary Index
- Journal :
- Journal of Scheduling
- Publication Type :
- Academic Journal
- Accession number :
- 178953447
- Full Text :
- https://doi.org/10.1007/s10951-023-00780-y