论文标题
通过（Max，+）最小化加权数量的迟来工作
Minimizing the Weighted Number of Tardy Jobs via (max,+)-Convolutions
论文作者
论文摘要
$ 1 \ MID \ Midσw_ju_j $问题要求确定 - 给定$ n $作业，每个$ n $ obsis的处理时间，重量和到期日 - 在任何一台机器的任何一台机器中，这些作业的最小加权数量的拖延工作都迟到。这是一个经典的调度问题，可以概括为背包和子集总和。由于Lawler和Moore [Managection'69]，最著名的伪多种算法售价为$ 1 \ Midσw_ju_j $，可追溯到60年代后期，运行时间为$ O（d _ {\ max} n）$的运行时间为$ o（d _ {\ max} n）$，其中$ n $ n $ n $ n $ n $ n as up the the $ d im and the Max} $} $} $} $}。 cygan \ emph {et al。}〜[icalp'19]的最新下部对knapsack表示，不能以$ \ widetilde {o} {o}（（n+d _ {\ max}）$ \ varepsilon $ nestion^$ nestiond $ nestife n $ widetilde {o}（n+d _ {n+d _ {n+d _合理的猜想。对于问题，这仍然留下了最著名的下限和上限之间的差距。 在本文中，我们设计了一种新的简单算法，价格为$ 1 \ MID \ MIDσW_JU_J $，该算法使用$（\ Max，+）$ - 卷积作为其主要工具，并且在几个参数范围内优于Lawler和Moore算法。特别是，取决于计算$（\ max，+）$ - 卷积的特定方法，其运行时间可以由 - $ \ widetilde {o}（n+d _ {\＃} d _ {\ max}^2）$。 - $ \ widetilde {o}（d _ {\＃} n +d^2 _ {\＃} d _ {\ max} w _ {\ max}）$。 - $ \ widetilde {o}（d _ {\＃} n +d _ {\＃} d _ {\ max} p _ {\ max}）$。 - $ \ widetilde {o}（n^2 +d _ {\ max} w^2 _ {\ max}）$。 - $ \ widetilde {o}（n^2 + d _ {\＃}（d _ {\ max} w _ {\ max}）^{1.5}）$。 在这里，$ d _ {\＃} $表示\ emph {不同}到期日期的数量，$ p _ {\ max} $表示任何作业的最大处理时间，而$ w _ {\ max} $表示任何工作的最大重量。
The $1 \mid \mid Σw_j U_j$ 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 Σw_j U_j$, due to Lawler and Moore [Management Science'69], dates back to the late 60s and has a running time of $O(d_{\max}n)$, where $n$ is the number of jobs and $d_{\max}$ is their maximal due date. A recent lower bound by Cygan \emph{et al.}~[ICALP'19] for Knapsack shows that $1 \mid \mid Σw_j U_j$ cannot be solved in $\widetilde{O}((n+d_{\max})^{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 Σw_j U_j$ 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 - $\widetilde{O}(n+d_{\#}d_{\max}^2)$. - $\widetilde{O}(d_{\#}n +d^2_{\#}d_{\max}w_{\max})$. - $\widetilde{O}(d_{\#}n +d_{\#}d_{\max}p_{\max})$. - $\widetilde{O}(n^2 +d_{\max}w^2_{\max})$. - $\widetilde{O}(n^2 + d_{\#}(d_{\max}w_{\max})^{1.5})$. Here, $d_{\#}$ denotes the number of \emph{different} due dates in the instance, $p_{\max}$ denotes the maximum processing time of any job, and $w_{\max}$ denotes the maximum weight of any job.
