Datum / čas
Date(s) - 24.01.
15:00 - 17:00
Kategorie
[Presenter] [Invited by]
Klaus Heeger Michael Pinedo
(Ben Gurion Uni) (New York Uni)
Minimizing the Weighted Number of Tardy Jobs is W[1]-hard
Jan 24, 2023 at 15 CET
Join online or offline on our Youtube channel: Scheduling seminar – YouTube
Abstract:
We consider the 1 || ∑ wj Uj 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 || ∑ wj Uj is W[1]-hard with respect to the number of different processing times in the input, as well as with respect to the number of different weights in the input. This, along with previous work, provides a complete picture for 1 || ∑ wj Uj from the perspective of parameterized complexity, as well as almost tight complexity bounds for the problem under the Exponential Time Hypothesis (ETH). Based on joint work with Danny Hermelin.