2020/03/16 by Amir Abboud, Karl Bringmann, Abboud, Amir +5 · 1 citation
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.2003.07113
14 pages, ICALP'20
arxiv created 2020/04/27 · arxiv updated 2020/04/28
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=maxi ti 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, based on ∀ ∃-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.