Faster minimization of tardy processing time on a single machine

DOI10.1007/S00453-022-00928-WMaRDI QIDQ2134746zbMATH OpenOpenAlexFDO

Authors Karl Bringmann, Nick Fischer, Danny Hermelin, Dvir Shabtay, Philip Wellnitz

Publication date 3 May 2022

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.07104

zbMATH Keywords

single machine schedulingpseudo-polynomial time algorithmfast polynomial multiplication(max, min)-convolutiontardy processing time

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Recommendations

• Minimizing the weighted number of tardy jobs via \((\max,+)\)-convolutions
• On minimizing the sum of \(k\) tardinesses
• New algorithms for minimizing the weighted number of tardy jobs on a single machine
• A faster algorithm for a due date assignment problem with tardy jobs
• Minimizing the number of tardy job units under release time constraints

Cites work

• scientific article; zbMATH DE number 7204473 (Why is no real title available?)
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems
• A faster pseudopolynomial time algorithm for subset sum
• A near-linear pseudopolynomial time algorithm for subset sum
• Bounds on Multiprocessing Timing Anomalies
• Introduction to algorithms.
• On problems equivalent to \((\min,+)\)-convolution
• Reducibility among combinatorial problems
• SETH-based lower bounds for subset sum and bicriteria path
• Simple multivariate polynomial multiplication

Cited in

(3)

• Quick minimization of tardy processing time on a single machine
• Minimizing the weighted number of tardy jobs via \((\max,+)\)-convolutions
• Computing generalized convolutions faster than brute force

This page was built for publication: Faster minimization of tardy processing time on a single machine

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2134746)