The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910347147870208 |
|---|---|
| author | Stoian, Mihail |
| author_facet | Stoian, Mihail |
| contents | We study the fundamental scheduling problem $1\|\sum p_jU_j$. Given a set of $n$ jobs with processing times $p_j$ and deadlines $d_j$, the problem is to select a subset of jobs such that the total processing time is maximized without violating the deadlines. In the midst of a flourishing line of research, Fischer and Wennmann have recently devised the sought-after $\widetilde O(P)$-time algorithm, where $P = \sum p_j$ is the total processing time of all jobs. This running time is optimal as it matches conditional lower bounds based on popular conjectures.
However, $P$ is not the sole parameter one could parameterize the running time by. Indeed, they explicitly leave open the question of whether a running time of $\widetilde O(n + \max d_j)$ or even $\widetilde O(n + \max p_j)$ is possible. In this work, we show, somewhat surprisingly, that by a refined implementation of their original algorithm, one can obtain the asked-for $\widetilde O(n + \max d_j)$-time algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_16847 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time Stoian, Mihail Data Structures and Algorithms Computational Complexity We study the fundamental scheduling problem $1\|\sum p_jU_j$. Given a set of $n$ jobs with processing times $p_j$ and deadlines $d_j$, the problem is to select a subset of jobs such that the total processing time is maximized without violating the deadlines. In the midst of a flourishing line of research, Fischer and Wennmann have recently devised the sought-after $\widetilde O(P)$-time algorithm, where $P = \sum p_j$ is the total processing time of all jobs. This running time is optimal as it matches conditional lower bounds based on popular conjectures. However, $P$ is not the sole parameter one could parameterize the running time by. Indeed, they explicitly leave open the question of whether a running time of $\widetilde O(n + \max d_j)$ or even $\widetilde O(n + \max p_j)$ is possible. In this work, we show, somewhat surprisingly, that by a refined implementation of their original algorithm, one can obtain the asked-for $\widetilde O(n + \max d_j)$-time algorithm. |
| title | The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2402.16847 |