Minimizing the weighted number of tardy jobs is W[1]-hard
Abstract
We consider the 1 | | ∑ w j U j problem, the problem of minimizing the weighted number of tardy jobs on a single machine. This problem is one of the most basic and fundamental problems in scheduling theory, with several different applications both in theory and practice. Using a reduction from the Multicolored Clique problem, we prove that 1 | | ∑ w j U j is W[1]-hard with respect to the number p # of different processing times in the input, as well as with respect to the number w # of different weights in the input. This, along with previous work, provides a complete picture for 1 | | ∑ w j U j from the perspective of parameterized complexity, as well as almost tight complexity bounds for the problem under the Exponential Time Hypothesis (ETH).
Fields of Study & Subjects
Scheduling and Optimization Algorithms
Optimization and Search Problems
Computability
Logic
AI Algorithms
Publication details
- Journal / source
- Journal of Computer and System Sciences
- Publisher
- Elsevier BV
- Volume
- 161
- Pages
- 103817–103817
- Publication date
- 21 May 2026
- Language
- EN