Metraipolis › archive › dc_f2a3ab178290

Test or Run? Scheduling Jobs of Unknown Length — arXiv:2608.30911

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.30911
License (as archived)
CC0-1.0
Archived
2026-10-17T10:07:15.947Z
SHA-256 of the archived text
22afd14276cc923ce48d2f2b749fc6875533a581fe5aecad30f744982ea558d1
Stable URL of this page
https://metraipolis.com/documento/dc_f2a3ab178290

How to cite

Test or Run? Scheduling Jobs of Unknown Length — arXiv:2608.30911 — arXiv (en), https://arxiv.org/abs/2608.30911 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f2a3ab178290 (Metraipolis archive dc_f2a3ab178290, sha256 22afd14276cc923ce48d2f2b749fc6875533a581fe5aecad30f744982ea558d1)
BibTeX
@misc{dcf2a3ab178290,
  title = {Test or Run? Scheduling Jobs of Unknown Length — arXiv:2608.30911},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.30911},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f2a3ab178290; sha256 22afd14276cc923ce48d2f2b749fc6875533a581fe5aecad30f744982ea558d1},
  year = {2026}
}

Archived text

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

A machine faces many jobs whose lengths are hidden. Spending one unit of time to inspect a job may reveal a short job that should be finished now, or it may reveal nothing useful while every other job waits. When should the machine keep looking, and when should it start working? We study natural variants of this question and provide optimal algorithms in both the worst-case and instance-optimal frameworks. The resulting algorithms are often quite simple, which may make them useful in practice.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-01 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.30911 — 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-10-17T10:00:01.295Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).