Metraipolis › archive › dc_82a2c6eebeae
On Randomized Online Span Minimization — arXiv:2608.08372
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.08372
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T09:16:43.067Z
- SHA-256 of the archived text
1d42fac9b0840f9b9171de9564f3aa2cf3a87499866620c08c7686903a09ecfb- Stable URL of this page
https://metraipolis.com/documento/dc_82a2c6eebeae
How to cite
On Randomized Online Span Minimization — arXiv:2608.08372 — arXiv (en), https://arxiv.org/abs/2608.08372 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_82a2c6eebeae (Metraipolis archive dc_82a2c6eebeae, sha256 1d42fac9b0840f9b9171de9564f3aa2cf3a87499866620c08c7686903a09ecfb)
BibTeX
@misc{dc82a2c6eebeae,
title = {On Randomized Online Span Minimization — arXiv:2608.08372},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.08372},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_82a2c6eebeae; sha256 1d42fac9b0840f9b9171de9564f3aa2cf3a87499866620c08c7686903a09ecfb},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.08372. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the online Busy Time scheduling model on a single machine of unbounded capacity, with non-preemptive jobs. In our setting, flexible jobs arrive online with a processing time and deadline, both of which become known to the algorithm at the job's arrival time. The goal is to schedule jobs on the machine to finish all jobs by their deadlines, so that the total time when the machine is turned on (busy time, also called span in this setting) is minimized. We present a randomized online algorithm with an exact competitive ratio of exactly (1 + e) < 3.72, where e is Euler's number, against an oblivious adversary, and show that no randomized algorithm can have a competitive ratio better than $e$ against an oblivious adversary. This lower bound holds even for algorithms that are allowed to restart jobs and are given lookahead. Previous work either dealt with special cases, or with deterministic algorithms, for which the known upper bound on the competitive ratio is 5 and the known lower bound is 4. Our findings offer fresh insights into randomization in online energy-aware scheduling. In the setting where jobs have uniform processing times, and a job that is started by the algorithm must be finished, we show that no deterministic algorithm can do better than 2, even when the jobs are agreeable. This deterministic lower bound also holds for uniform processing times and restarts in the scenario where a job's deadline is only revealed at its starting deadline. For Capacitated Busy Time with p_max-lookahead, we obtain a deterministic online algorithm with competitive ratio at most 8 and a randomized online algorithm with competitive ratio at most (4+ e) < 6.72, against an oblivious adversary. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-11 in cs.DS). Categorie arXiv: Data Structures and Algorithms (cs.DS). Pagina del lavoro: https://arxiv.org/abs/2608.08372 — 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-19T09:13:57.839Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).