Approximating weighted completion time via stronger negative correlation
Minimizing the weighted completion time of jobs in the unrelated parallel machines model is a fundamental scheduling problem. The first (3/2−𝑐) –approximation algorithm for this problem, for some constant 𝑐>0 , was obtained in the work of Bansal et al. (SIAM J Comput, 2021). A key ingredient in...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer US
2024
|
| Online Access: | https://hdl.handle.net/1721.1/156081 |