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/

Zendy Plus

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

Zendy Tools

Zendy Open

The starting point of this paper is the problem of scheduling $n$ jobs withprocessing times and due dates on a single machine so as to minimize the totalprocessing time of tardy jobs, i.e., $1||\sum p_j U_j$. This problem wasidentified by Bringmann et al. (Algorithmica 2022) as a naturalsubquadratic-time special case of the classic $1||\sum w_j U_j$ problem, whichlikely requires time quadratic in the total processing time $P$, because of afine-grained lower bound. Bringmann et al.~obtain their $\tilde{O}(P^{7/4})$time scheduling algorithm through a new variant of convolution, dubbed Max-MinSkewed Convolution, which they solve in $\tilde{O}(n^{7/4})$ time. Our maintechnical contribution is a faster and simpler convolution algorithm running in$\tilde{O}(n^{5/3})$ time. It implies an $\tilde{O}(P^{5/3})$ time algorithmfor $1||\sum p_j U_j$, but may also be of independent interest.  Inspired by recent developments for the Subset Sum and Knapsack problems, westudy $1||\sum 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 newdynamic programming formulation, lead to an $\tilde{O}(n+p_{\max}^3)$ timealgorithm. Moreover, in the setting with multiple machines, we use similartechniques to get an $n \cdot p_{\max}^{O(m)}$ time algorithm for $Pm||\sum p_jU_j$.  Finally, we point out that the considered problems exhibit a particulartriangular block structure in the constraint matrices of their ILPformulations. In light of recent ILP research, a question that arises iswhether one can devise a generic algorithm for such a class of ILPs. We give anegative answer to this question: we show that already a slight generalizationof the structure of the scheduling ILP leads to a strongly NP-hard problem.

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