Metraipolis › archive › dc_8d67af8edd79

Compressing the Lawler-Moore Dynamic Program for Weighted Tardy Jobs — arXiv:2610.41821

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.41821
License (as archived)
CC0-1.0
Archived
2026-11-03T05:49:22.691Z
SHA-256 of the archived text
3d71be9b92025628c54ec2f41f96dd6d090683949be05e3d914640c1d3a19730
Stable URL of this page
https://metraipolis.com/documento/dc_8d67af8edd79

How to cite

Compressing the Lawler-Moore Dynamic Program for Weighted Tardy Jobs — arXiv:2610.41821 — arXiv (en), https://arxiv.org/abs/2610.41821 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8d67af8edd79 (Metraipolis archive dc_8d67af8edd79, sha256 3d71be9b92025628c54ec2f41f96dd6d090683949be05e3d914640c1d3a19730)
BibTeX
@misc{dc8d67af8edd79,
  title = {Compressing the Lawler-Moore Dynamic Program for Weighted Tardy Jobs — arXiv:2610.41821},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.41821},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8d67af8edd79; sha256 3d71be9b92025628c54ec2f41f96dd6d090683949be05e3d914640c1d3a19730},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41821. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The classic scheduling problem of minimizing the total weight of tardy jobs ($P_m||\sum_jw_jU_j$) asks for a schedule of jobs each with a processing time, weight, and due date on a constant number of parallel identical machines. A job is late in a schedule if it completes after its due date, and an optimal schedule is one where the total weight of all late jobs is minimized. The classic dynamic programming algorithm of Lawler and Moore [Manag. Sci., 1969] solves this problem in $O(nd_{\max}^m)$ where $n$ is the number of jobs, $d_{\max}$ is the maximum due date of any job, and $m$ is the number of identical machines. We show that it is sufficient to only compute part of the dynamic program and obtain the running time $\tilde{O}(n + d_{\max}^{m + 1})$ where $\tilde{O}$ suppresses polylogarithmic factors. This affirmatively answers the open question posed by Hermelin, Molter, and Shabtay [INFORMS J. Comput., 2024], whether a running time of $\tilde{O}(n + d_{\max}^2)$ is possible on a single machine.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.41821 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T05:34:47.023Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).