Scheduling lower bounds via and Subset Sum

Abstract

Given N instances (X1, t1), . . ., (XN, tN) of Subset Sum, the AND Subset Sum problem asks to determine whether all of these instances are yes-instances; that is, whether each set of integers Xi has a subset that sums up to the target integer ti. We prove that this problem cannot be solved in time Oe((N · tmax)1−ε), for tmax = maxi ti and any ε > 0, assuming the ∀∃ Strong Exponential Time Hypothesis (∀∃-SETH). We then use this result to exclude Oe(n + Pmax · n1−ε)-time algorithms for several scheduling problems on n jobs with maximum processing time Pmax, assuming ∀∃-SETH. These include classical problems such as 1||P wjUj, the problem of minimizing the total weight of tardy jobs on a single machine, and P2||P Uj, the problem of minimizing the number of tardy jobs on two identical parallel machines.