文章基本信息

标题：Faster Minimization of Tardy Processing Time on a Single Machine
本地全文：下载
作者：Karl Bringmann ; Nick Fischer ; Danny Hermelin 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：168
页码：19:1-19:12
DOI：10.4230/LIPIcs.ICALP.2020.19
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：This paper is concerned with the 1 â^' 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 â<. 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 â^' p_jU_j, each improving on Lawler and Mooreâs algorithm in a different scenario: - Our first algorithm runs in OÌf(P^{7/4}) time, and outperforms Lawler and Mooreâs algorithm in instances where n = ÏÌf(P^{3/4}). - Our second algorithm runs in OÌf(min{P â<. D_#, P + D}) time, where D_# is the number of different due dates in the instance, and D is the sum of all different due dates. This algorithm improves on Lawler and Mooreâs algorithm when n = ÏÌf(D_#) or n = ÏÌf(D/P). Further, it extends the known OÌf(P) algorithm for the single due date special case of 1 â^' p_jU_j in a natural way. 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.
关键词：Weighted number of tardy jobs; sumsets; convolutions