2026/05/21 by Klaus Heeger, Danny Hermelin · 1 citation
Computer Science · Engineering · Mathematics · #Combinatorics #Computability, Logic, AI Algorithms #Discrete mathematics #Exponential function #Exponential time hypothesis #Mathematical optimization #Mathematics #Optimization and Search Problems #Parameterized complexity #Perspective (graphical) #Scheduling (production processes) #Scheduling and Optimization Algorithms
paper · doi:10.1016/j.jcss.2026.103817
published in Journal of Computer and System Sciences 161, 103817 (Elsevier BV)
openalex created_date 2024/01/05 · openalex publication_date 2026/05/21 · openalex updated_date 2026/07/31
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).