Metraipolis › archive › dc_f08a58eec9ef
Scheduling with Mandatory Breaks: NP-Hardness and an Additive-One Approximation — arXiv:2609.34254
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.34254
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T00:19:00.509Z
- SHA-256 of the archived text
1b3fd31c7fc24b006ac41b8bb89c91e85103d5d37ff0bea51412b8a8fe07b2fb- Stable URL of this page
https://metraipolis.com/documento/dc_f08a58eec9ef
How to cite
Scheduling with Mandatory Breaks: NP-Hardness and an Additive-One Approximation — arXiv:2609.34254 — arXiv (en), https://arxiv.org/abs/2609.34254 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f08a58eec9ef (Metraipolis archive dc_f08a58eec9ef, sha256 1b3fd31c7fc24b006ac41b8bb89c91e85103d5d37ff0bea51412b8a8fe07b2fb)
BibTeX
@misc{dcf08a58eec9ef,
title = {Scheduling with Mandatory Breaks: NP-Hardness and an Additive-One Approximation — arXiv:2609.34254},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.34254},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f08a58eec9ef; sha256 1b3fd31c7fc24b006ac41b8bb89c91e85103d5d37ff0bea51412b8a8fe07b2fb},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.34254. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In classical fixed-interval scheduling, each job of a given set must be processed during a prescribed time interval. The goal is to assign each job to exactly one machine such that no two jobs assigned to the same machine overlap in their interiors, and the number of machines used is minimized. Without further constraints this is interval graph coloring and is solvable in polynomial time through greedy approaches. We study a variant in which every used machine must remain idle during a contiguous \emph{break} of prescribed length $x$ somewhere in the scheduling horizon. We show that this additional constraint makes the problem hard, except when $x\le1$. First, for every fixed $x\ge2$, deciding whether $k$ machines suffice for the assignment of a given set of jobs is NP-complete, even when all coordinates are bounded linearly in the number of jobs, so machine minimization is strongly NP-hard. Second, for $x=1$, we give a polynomial-time algorithm that solves the problem exactly. Finally, we give a deterministic polynomial-time algorithm that, on every feasible instance, outputs a schedule using at most $\OPT+1$ machines, where $\OPT$ is the true minimum. Unless $\mathrm{P}=\mathrm{NP}$, no polynomial-time algorithm guarantees $\OPT$ machines for any fixed $x\ge2$, so the additive guarantee of one is best possible.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.34254 — 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-07T23:56:21.770Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).