@online{Abboud_arXIv2003.07113,
TITLE = {Scheduling Lower Bounds via {AND} Subset Sum},
AUTHOR = {Abboud, Amir and Bringmann, Karl and Hermelin, Danny and Shabtay, Dvir},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2003.07113},
EPRINT = {2003.07113},
EPRINTTYPE = {arXiv},
YEAR = {2020},
MARGINALMARK = {$\bullet$},
ABSTRACT = {Given $N$ instances $(X_1,t_1),\ldots,(X_N,t_N)$ 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 $X_i$ has a subset that sums up to the target integer $t_i$. We prove that this problem cannot be solved in time $\tilde{O}((N \cdot t_{max})^{1-\epsilon})$, for $t_{max}=\max_i t_i$ and any $\epsilon > 0$, assuming the $\forall \exists$ Strong Exponential Time Hypothesis ($\forall \exists$-SETH). We then use this result to exclude $\tilde{O}(n+P_{max} \cdot n^{1-\epsilon})$-time algorithms for several scheduling problems on $n$ jobs with maximum processing time $P_{max}$, based on $\forall \exists$-SETH. These include classical problems such as $1||\sum w_jU_j$, the problem of minimizing the total weight of tardy jobs on a single machine, and $P_2||\sum U_j$, the problem of minimizing the number of tardy jobs on two identical parallel machines.},
}