Metraipolis › archive › dc_747efff7d656

Better Late Than Never: Online Flow Time Scheduling with Online Estimates — arXiv:2609.07402

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.07402
License (as archived): CC0-1.0
Archived: 2026-10-16T15:31:51.013Z
SHA-256 of the archived text: b975bcc6ae6479240182f7820ebb984c22f12bbed85ab52f371cc574130fbbc7
Stable URL of this page: https://metraipolis.com/documento/dc_747efff7d656

How to cite

Better Late Than Never: Online Flow Time Scheduling with Online Estimates — arXiv:2609.07402 — arXiv (en), https://arxiv.org/abs/2609.07402 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_747efff7d656 (Metraipolis archive dc_747efff7d656, sha256 b975bcc6ae6479240182f7820ebb984c22f12bbed85ab52f371cc574130fbbc7)

BibTeX

@misc{dc747efff7d656,
  title = {Better Late Than Never: Online Flow Time Scheduling with Online Estimates — arXiv:2609.07402},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.07402},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_747efff7d656; sha256 b975bcc6ae6479240182f7820ebb984c22f12bbed85ab52f371cc574130fbbc7},
  year = {2026}
}

Archived text

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

In the classical online flow-time scheduling problem on a single machine, jobs arrive over time and must be processed to minimize the total time they spend in the system: for over fifty years, we have known that SRPT is an optimal online algorithm. But this algorithm requires exactness in two different ways: (a) job sizes must be known exactly, and (b) they must be revealed as soon as the job arrives. Recent work relaxed each of these assumptions separately: there are algorithms based on knowing approximate sizes (given when the job arrives), or based on knowing (exact) sizes at some point before the remaining size gets too small. Nonetheless, prior to this work, there was no known approach to relax both assumptions simultaneously. In this work, we consider a model that demands much less: When we process a job, at some point in time between when we complete an $\varepsilon$-fraction and a $(1-\varepsilon)$-fraction of its unknown processing requirement, we are informed that the job is ``somewhere in the middle''. Finally, when the job has received its desired amount of processing, we are informed of its completion. No other information is shared about the job. We give an $O(1/\varepsilon^2)$-competitive algorithm for this model. Slightly more generally, we assume that an algorithm receives a $\mu$-approximate estimate of each job's processing time at some time before we complete a $(1-\varepsilon)$-fraction of its processing. Our algorithm is $O(\mu/\varepsilon)$-competitive, and we show that this is asymptotically optimal. It is a surprisingly natural variant of the multilevel feedback algorithm (MLF) and it is parameter-oblivious: it does not need to know $\mu$ or $\varepsilon$ upfront. The core analytical contribution is to robustify the dual-fitting framework for this problem to handle jobs for which we have not yet received estimates.

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