Metraipolis › archive › dc_34c9b2b9ecfa

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-03T08:24:08.172Z
SHA-256 of the archived text
1cbcb7baa7ac2a2e14c9940ca445f38dba1f8d15930791dffed506f2722008a7
Stable URL of this page
https://metraipolis.com/documento/dc_34c9b2b9ecfa

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_34c9b2b9ecfa (Metraipolis archive dc_34c9b2b9ecfa, sha256 1cbcb7baa7ac2a2e14c9940ca445f38dba1f8d15930791dffed506f2722008a7)
BibTeX
@misc{dc34c9b2b9ecfa,
  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_34c9b2b9ecfa; sha256 1cbcb7baa7ac2a2e14c9940ca445f38dba1f8d15930791dffed506f2722008a7},
  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-03T08:07:53.813Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).