Metraipolis › archive › dc_b97cc10570bb
Precedence Constraint Scheduling on a Fixed Number of Machines — arXiv:2611.09392
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.09392
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-09T22:47:12.656Z
- SHA-256 of the archived text
6dc56d21bb82da2506f1104c6ddd756d0ab74755cef65faaff9b9ceaa8509565- Stable URL of this page
https://metraipolis.com/documento/dc_b97cc10570bb
How to cite
Precedence Constraint Scheduling on a Fixed Number of Machines — arXiv:2611.09392 — arXiv (en), https://arxiv.org/abs/2611.09392 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b97cc10570bb (Metraipolis archive dc_b97cc10570bb, sha256 6dc56d21bb82da2506f1104c6ddd756d0ab74755cef65faaff9b9ceaa8509565)
BibTeX
@misc{dcb97cc10570bb,
title = {Precedence Constraint Scheduling on a Fixed Number of Machines — arXiv:2611.09392},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.09392},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b97cc10570bb; sha256 6dc56d21bb82da2506f1104c6ddd756d0ab74755cef65faaff9b9ceaa8509565},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.09392. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We give a deterministic exact algorithm for $P_m\mid\mathrm{prec},p_j=1\mid C_{\max}$ for every fixed $m\ge3$. The algorithm constructs an optimum schedule in $$ O(L)+m^{O(m^2)}\, n^{6m^2+13m+1} \, {\log n} $$ elementary RAM operations, where $n \ge 2$ is the number of jobs and $L$ is the binary input length. Its word size is $O(m^2 \log n)$ bits. An implementation with a fixed number of tapes uses $O(L)+m^{O(m^2)} \, n^{12m^2+26m+2} \, \log^3 n$ steps. For three machines the respective polynomial degrees are $94$ and $188$, apart from the displayed logarithmic factors.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2611.09392 — 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-09T22:40:29.876Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).