@online{Bringmann_arXiv2003.07104,
TITLE = {Faster Minimization of Tardy Processing Time on a Single Machine},
AUTHOR = {Bringmann, Karl and Fischer, Nick and Hermelin, Danny and Shabtay, Dvir and Wellnitz, Philip},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2003.07104},
EPRINT = {2003.07104},
EPRINTTYPE = {arXiv},
YEAR = {2020},
ABSTRACT = {This paper is concerned with the $1||\sum p_jU_j$ problem, the problem of
minimizing the total processing time of tardy jobs on a single machine. This is
not only a fundamental scheduling problem, but also a very important problem
from a theoretical point of view as it generalizes the Subset Sum problem and
is closely related to the 0/1-Knapsack problem. The problem is well-known to be
NP-hard, but only in a weak sense, meaning it admits pseudo-polynomial time
algorithms. The fastest known pseudo-polynomial time algorithm for the problem
is the famous Lawler and Moore algorithm which runs in $O(P \cdot n)$ time,
where $P$ is the total processing time of all $n$ jobs in the input. This
algorithm has been developed in the late 60s, and has yet to be improved to
date.
In this paper we develop two new algorithms for $1||\sum p_jU_j$, each
improving on Lawler and Moore's algorithm in a different scenario. Both
algorithms rely on basic primitive operations between sets of integers and
vectors of integers for the speedup in their running times. The second
algorithm relies on fast polynomial multiplication as its main engine, while
for the first algorithm we define a new "skewed" version of
$(\max,\min)$-convolution which is interesting in its own right.
},
}