← 研踪 PaperTrailarXiv:2611.24201 · v1
A (12/11+eps)-Approximation for Nonpreemptive Throughput Maximization
首次提交 2026-11-18 18:38
版本更新 2026-11-18 18:38
雷达观测 2026-11-19 15:04
摘要
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 , we give a randomized -approximation. This improves the recent -approximation of Alexander Armbruster, Fabrizio Grandoni, Antoine Tinguely, and Andreas Wiese and the -approximation of Tong and Xu. For binary-encoded integral inputs, our algorithm runs in time , where is the input length.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-18 18:38 · 最新观测版本
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 , we give a randomized -approximation. This improves the recent -approximation of Alexander Armbruster, Fabrizio Grandoni, Antoine Tinguely, and Andreas Wiese and the -approximation of Tong and Xu. For binary-encoded integral inputs, our algorithm runs in time , where is the input length.
查看此版本解读 →查看此版本原文 ↗