A (12/11+eps)-Approximation for Nonpreemptive Throughput Maximization
We study unweighted nonpreemptive throughput maximization on an arbitrary number of identical machines: each job has a processing time and a release--deadline window, and the goal is to schedule as many jobs as possible. For every fixed $\varepsilon>0$, we give a randomized $(12/11+\varepsilon)$-approximation. This improves the recent $(4/3+\varepsilon)$-approximation of Alexander Armbruster, Fabrizio Grandoni, Antoine Tinguely, and Andreas Wiese and the $(17/13+\varepsilon)$-approximation of Tong and Xu. For binary-encoded integral inputs, our algorithm runs in time $n^{O_\varepsilon(1)}\operatorname{poly}(N)$, where $N$ is the input length.
Authors
- Stanislav Moiseev (ORCID: https://orcid.org/0009-0007-0599-8999)
- Andrey Borisovich Kupavskii (ORCID: https://orcid.org/0000-0002-8313-9598)
- Mikhail Cherniavskii (ORCID: https://orcid.org/0000-0002-6486-054X)
- Михаил Кошелев
- Alexander Shekhovtsov (ORCID: https://orcid.org/0000-0003-0678-8954)
- Fedor Ozhegov
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-18
- DOI
- https://doi.org/10.48550/arxiv.2611.24201
- Primary Topic
- Scheduling and Optimization Algorithms
- Type
- preprint