On Minimizing Tardy Processing Time, Max-Min Skewed Convolution, and Triangular Structured ILPs

The starting point of this paper is the problem of scheduling n jobs with processing times and due dates on a single machine so as to minimize the total processing time of tardy jobs, i.e., 1 | | p j U j . This problem was identified by Bringmann et al. (Algorithmica 2022) as a natural subquadratic-time special case of the classic 1 | | w j U j problem, which likely requires time quadratic in the total processing time P , because of a fine-grained lower bound. Bringmann et al. obtain their O(P 7/4 ) time scheduling algorithm through a new variant of convolution, dubbed Max-Min Skewed Convolution, which they solve in O(n 7/4 ) time. Our main technical contribution is a faster and simpler convolution algorithm running in O(n 5/3 ) time. It implies an O(P 5/3 ) time algorithm for 1 | | p j U j , but may also be of independent interest. Inspired by recent developments for the Subset Sum and Knapsack problems, we study 1 | | p j U j parameterized by the maximum job processing time p max . With proximity techniques borrowed from integer linear programming (ILP), we show structural properties of the problem that, coupled with a new dynamic programming formulation, lead to an O(n + p 3 max ) time algorithm. Moreover, in the setting with multiple machines, we use similar techniques to get an n • p O(m) max time algorithm for P m | | p j U j . Finally, we point out that the considered problems exhibit a particular triangular block structure in the constraint matrices of their ILP formulations. In light of recent ILP research, a question that arises is whether one can devise a generic algorithm for such a class of ILPs. We give a negative answer to this question: we show that already a slight generalization of the structure of the scheduling ILP leads to a strongly NP-hard problem.