Faster minimization of tardy processing time on a single machine

DOI10.1007/s00453-022-00928-wOpenAlexW4220919512MaRDI QIDQ2134746

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

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)

Related Items

Quick minimization of tardy processing time on a single machine ⋮ Computing generalized convolutions faster than brute force

Cites Work

• Unnamed Item
• Unnamed Item
• Simple multivariate polynomial multiplication
• A Faster Pseudopolynomial Time Algorithm for Subset Sum
• A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
• On Problems Equivalent to (min,+)-Convolution
• Reducibility among Combinatorial Problems
• SETH-Based Lower Bounds for Subset Sum and Bicriteria Path
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems
• Bounds on Multiprocessing Timing Anomalies

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