アイテム詳細

要旨

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.