2024/02/26 by Mihail Stoian, Stoian, Mihail
Business, Management and Accounting · Economics, Econometrics and Finance · #Consumer Market Behavior and Pricing #Economic theories and models #Supply Chain and Inventory Management
paper · pdf · doi:10.48550/arxiv.2402.16847
We study the fundamental scheduling problem 1‖∑ pjUj. Given a set of n jobs with processing times pj and deadlines dj, 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 \widetilde O(P)-time algorithm, where P = ∑ pj 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 \widetilde O(n + max dj) or even \widetilde O(n + max pj) is possible. In this work, we show, somewhat surprisingly, that by a refined implementation of their original algorithm, one can obtain the asked-for \widetilde O(n + max dj)-time algorithm.