Minimizing the Weighted Number of Tardy Jobs is W[1]-hard

2024/01/03 by Heeger, Klaus, Hermelin, Danny
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2401.01740

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. 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).

Related

• Minimizing the weighted number of tardy jobs is W[1]-hard
• New Algorithms for Minimizing the Weighted Number of Tardy Jobs On a Single Machine
• Single Machine Batch Scheduling to Minimize the Weighted Number of Tardy Jobs
• Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates
• Minimizing the Weighted Number of Tardy Jobs via (max,+)-Convolutions