Vladimir Yanovski, Israel A. Wagner, et al.
Ann. Math. Artif. Intell.
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 O˜((N⋅tmax)1−ε), for tmax=maxiti and any ε>0, assuming the ∀∃ Strong Exponential Time Hypothesis (∀∃-SETH). We then use this result to exclude O˜(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||∑wjUj, the problem of minimizing the total weight of tardy jobs on a single machine, and P2||∑Uj, the problem of minimizing the number of tardy jobs on two identical parallel machines.
Vladimir Yanovski, Israel A. Wagner, et al.
Ann. Math. Artif. Intell.
Salvatore Certo, Anh Pham, et al.
Quantum Machine Intelligence
Richard M. Karp, Raymond E. Miller
Journal of Computer and System Sciences
Daniel J. Costello Jr., Pierre R. Chevillat, et al.
ISIT 1997