Abstract

We consider the 1∣∣∑wJUj1||\sum 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∣∣∑wJUj1||\sum w_J U_j is W[1]-hard with respect to the number p#p_{\#} of different processing times in the input, as well as with respect to the number w#w_{\#} of different weights in the input. This, along with previous work, provides a complete picture for 1∣∣∑wJUj1||\sum 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).

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.