Key points are not available for this paper at this time.
We study the fundamental scheduling problem 1\| pⱼUⱼ. Given a set of n jobs with processing times pⱼ and deadlines dⱼ, the problem is to select a subset of jobs such that the total processing time is maximized without violating the deadlines. In the midst of a flourishing line of research, Fischer and Wennmann have recently devised the sought-after O (P) -time algorithm, where P = pⱼ is the total processing time of all jobs. This running time is optimal as it matches conditional lower bounds based on popular conjectures. However, P is not the sole parameter one could parameterize the running time by. Indeed, they explicitly leave open the question of whether a running time of O (n + dⱼ) or even O (n + pⱼ) is possible. In this work, we show, somewhat surprisingly, that by a refined implementation of their original algorithm, one can obtain the asked-for O (n + dⱼ) -time algorithm.
Mihail Stoian (Mon,) studied this question.