@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},
ABSTRACT = {Given $N$ instances $(X_1,t_1),\ldots,(X_N,t_N)$ of Subset Sum, the AND<br>Subset Sum problem asks to determine whether all of these instances are<br>yes-instances; that is, whether each set of integers $X_i$ has a subset that<br>sums up to the target integer $t_i$. We prove that this problem cannot be<br>solved in time $\tilde{O}((N \cdot t_{max})^{1-\epsilon})$, for $t_{max}=\max_i<br>t_i$ and any $\epsilon > 0$, assuming the $\forall \exists$ Strong Exponential<br>Time Hypothesis ($\forall \exists$-SETH). We then use this result to exclude<br>$\tilde{O}(n+P_{max} \cdot n^{1-\epsilon})$-time algorithms for several<br>scheduling problems on $n$ jobs with maximum processing time $P_{max}$, based<br>on $\forall \exists$-SETH. These include classical problems such as $1||\sum<br>w_jU_j$, the problem of minimizing the total weight of tardy jobs on a single<br>machine, and $P_2||\sum U_j$, the problem of minimizing the number of tardy<br>jobs on two identical parallel machines.<br>},
}