English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The $1 \mid \mid \Sigma w_j U_j$ problem asks to determine -- given $n$ jobseach with its own processing time, weight, and due date -- the minimum weightednumber of tardy jobs in any single machine non-preemptive schedule for thesejobs. This is a classical scheduling problem that generalizes both Knapsack,and Subset Sum. The best known pseudo-polynomial algorithm for $1 \mid \mid\Sigma w_j U_j$, due to Lawler and Moore [Management Science'69], dates back tothe late 60s and has a running time of $O(d_{\max}n)$, where $n$ is the numberof 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 \Sigma 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 gapbetween 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 w_jU_j$ that uses $(\max,+)$-convolutions as its main tool, and outperforms theLawler and Moore algorithm under several parameter ranges. In particular,depending on the specific method of computing $(\max,+)$-convolutions, itsrunning 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 theinstance, $p_{\max}$ denotes the maximum processing time of any job, and$w_{\max}$ denotes the maximum weight of any job.

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