Metraipolis › archive › dc_de270a8e12db
Multidimensional Resource Scheduling with Small Demands — arXiv:2609.39349
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.39349
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T15:17:08.811Z
- SHA-256 of the archived text
e9a398130198b097291fa0223031bfd1c87b39ba80425642233770fed4582e25- Stable URL of this page
https://metraipolis.com/documento/dc_de270a8e12db
How to cite
Multidimensional Resource Scheduling with Small Demands — arXiv:2609.39349 — arXiv (en), https://arxiv.org/abs/2609.39349 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_de270a8e12db (Metraipolis archive dc_de270a8e12db, sha256 e9a398130198b097291fa0223031bfd1c87b39ba80425642233770fed4582e25)
BibTeX
@misc{dcde270a8e12db,
title = {Multidimensional Resource Scheduling with Small Demands — arXiv:2609.39349},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.39349},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_de270a8e12db; sha256 e9a398130198b097291fa0223031bfd1c87b39ba80425642233770fed4582e25},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.39349. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study multidimensional resource scheduling. Each job $i$ has a $d$-dimensional resource-demand vector $v_i$ and a processing time $s_i$. The scheduler assigns a start time to each job, subject to the constraint that, at every time, the total demand of the jobs being processed does not exceed $1$ in any resource dimension. The objective is to minimize the makespan. We focus on the regime in which every individual resource demand is small. We ask whether the favorable \emph{small-vector phenomenon} known for multidimensional vector packing, which corresponds to the special case of unit processing times, extends to jobs with heterogeneous processing times. The key difficulty is that arbitrary processing times create temporal interactions across multiple duration scales: a long job may overlap many shorter jobs, while feasibility must be maintained throughout every job's execution interval. We prove that the small-vector phenomenon persists in this temporal setting. For any $0<\epsilon<1/4$, after normalizing the maximum processing time to $1$, if every coordinate of every demand vector is at most $O(\epsilon^2/\log(d/\epsilon))$, we give a randomized offline algorithm that produces a schedule with expected makespan at most $ (1+6\epsilon)\mathrm{OPT}+3$. Thus, sufficiently small resource demands admit asymptotically near-optimal schedules in arbitrary dimension, despite heterogeneous processing times. We also obtain constant competitive ratios in the online setting. Let $T$ denote the ratio between the maximum and minimum processing times. If every coordinate is at most $O(1/(\log d\log T))$, we give a randomized $O(1)$-competitive algorithm, with a competitive ratio independent of both $d$ and $T$. We further derandomize our approach, obtaining a deterministic $O(1)$-competitive algorithm under a comparable smallness assumption.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-01 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.39349 — 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-07T14:50:37.639Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).