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 |
| _version_ | 1824458285134118912 |
|---|---|
| author | Baveja, Alok Qu, Xiaoran Srinivasan, Aravind |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Baveja, Alok Qu, Xiaoran Srinivasan, Aravind |
| author_sort | Baveja, Alok |
| collection | MIT |
| description | 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 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. |
| first_indexed | 2024-09-23T14:07:18Z |
| format | Article |
| id | mit-1721.1/156081 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2025-02-19T04:23:27Z |
| publishDate | 2024 |
| publisher | Springer US |
| record_format | dspace |
| spelling | mit-1721.1/1560812025-01-12T04:41:40Z Approximating weighted completion time via stronger negative correlation Baveja, Alok Qu, Xiaoran Srinivasan, Aravind Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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 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. 2024-08-14T16:10:01Z 2024-08-14T16:10:01Z 2023-03-30 2024-08-10T03:27:17Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/156081 Baveja, A., Qu, X. & Srinivasan, A. Approximating weighted completion time via stronger negative correlation. J Sched 27, 319–328 (2024). en https://doi.org/10.1007/s10951-023-00780-y Journal of Scheduling Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature application/pdf Springer US Springer US |
| spellingShingle | Baveja, Alok Qu, Xiaoran Srinivasan, Aravind Approximating weighted completion time via stronger negative correlation |
| title | Approximating weighted completion time via stronger negative correlation |
| title_full | Approximating weighted completion time via stronger negative correlation |
| title_fullStr | Approximating weighted completion time via stronger negative correlation |
| title_full_unstemmed | Approximating weighted completion time via stronger negative correlation |
| title_short | Approximating weighted completion time via stronger negative correlation |
| title_sort | approximating weighted completion time via stronger negative correlation |
| url | https://hdl.handle.net/1721.1/156081 |
| work_keys_str_mv | AT bavejaalok approximatingweightedcompletiontimeviastrongernegativecorrelation AT quxiaoran approximatingweightedcompletiontimeviastrongernegativecorrelation AT srinivasanaravind approximatingweightedcompletiontimeviastrongernegativecorrelation |