Minimizing the weighted number of tardy jobs is W[1]-hard

DOI10.1016/J.JCSS.2026.103817MaRDI QIDQ7307945zbMATH OpenFDO

Authors Klaus Heeger, Danny Hermelin

Publication date 3 August 2026

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCSS.2026.103817

Mathematics Subject Classification ID

Computer science (68-XX)

Cites work

• A Functional Equation and its Application to Resource Allocation and Sequencing Problems
• A survey of single machine scheduling to minimize weighted number of tardy jobs
• Algorithms for Scheduling Independent Tasks
• An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
• Can you beat treewidth?
• Conditional lower bounds for sparse parameterized 2-CSP: a streamlined proof
• Faster minimization of tardy processing time on a single machine
• Fundamentals of parameterized complexity
• Heterogeneous-criteria scheduling: Minimizing weighted number of tardy jobs and weighted completion time
• Integer Programming with a Fixed Number of Variables
• Minimizing the weighted number of tardy jobs via (,+)-convolutions
• New algorithms for minimizing the weighted number of tardy jobs on a single machine
• On minimizing tardy processing time, Max-Min skewed convolution, and triangular structured ILPs
• On problems equivalent to \((\min,+)\)-convolution
• On the complexity of k-SAT
• On the parameterized complexity of multiple-interval graph problems
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Parameterized complexity of machine scheduling: 15 open problems
• Parameterizing by the number of numbers
• Polynomial kernels for weighted problems
• Polynomiality for Bin Packing with a Constant Number of Item Types
• Quick minimization of tardy processing time on a single machine
• Reducibility among combinatorial problems
• Serial batching to minimize the weighted number of tardy jobs
• Strong computational lower bounds via parameterized complexity
• The subspace flatness conjecture and faster integer programming

This page was built for publication: Minimizing the weighted number of tardy jobs is W[1]-hard

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