Minimizing the Weighted Number of Tardy Jobs via (max,+)-Convolutions

The 1 mid mid Sigma wj Uj problem asks to determine -- given n jobs each with its own processing time, weight, and due date -- the minimum weighted number of tardy jobs in any single machine non-preemptive schedule for these jobs. This is a classical scheduling problem that generalizes both Knapsack, and Subset Sum. The best known pseudo-polynomial algorithm for 1 mid mid Sigma wj Uj, due to Lawler and Moore [Management Science'69], dates back to the late 60s and has a running time of O(dmaxn), where n is the number of jobs and dmax is their maximal due date. A recent lower bound by Cygan et al.~[ICALP'19] for Knapsack shows that 1 mid mid Sigma wj Uj cannot be solved in widetildeO((n+dmax)2-varepsilon) time, for any varepsilon > 0, under a plausible conjecture. This still leaves a gap between the best known lower bound and upper bound for the problem. In this paper we design a new simple algorithm for 1 mid mid Sigma wj Uj that uses (max,+)-convolutions as its main tool, and outperforms the Lawler and Moore algorithm under several parameter ranges. In particular, depending on the specific method of computing (max,+)-convolutions, its running time can be bounded by - widetildeO(n+d#dmax2). - widetildeO(d#n +d2#dmaxwmax). - widetildeO(d#n +d#dmaxpmax). - widetildeO(n2 +dmaxw2max). - widetildeO(n2 + d#(dmaxwmax)1.5). Here, d# denotes the number of different due dates in the instance, pmax denotes the maximum processing time of any job, and wmax denotes the maximum weight of any job.