论文标题
安排下限通过和子集总和
Scheduling Lower Bounds via AND Subset Sum
论文作者
论文摘要
给定$ n $ instances $（x_1，t_1），\ ldots，（x_n，t_n）$ subset sum，和子集总和问题要求确定所有这些实例是否均为Yes-Instances；也就是说，是否每组整数$ x_i $都有一个子集总计到目标整数$ t_i $。我们证明，这个问题无法在时间$ \ tilde {o}（（（n \ cdot t_ {max}））^{1-ε}）$，对于$ t_ {max} = \ max_i t_i $和任何$ε> 0 $，假设$ \ forall \ forall peplell \ forall $ strong uppersential time helpothesiss $ $ \ forsist $ \ forsist（然后，我们使用此结果来排除$ \ tilde {o}（n+p_ {max} \ cdot n^{1-ε}）$ - 基于$ n $ jobs上的几种调度问题的时间算法，具有最大处理时间$ p_ {max {max} $，基于$ \ forall \ forall p_ forall \ everall \ earmest $ seth。这些包括经典问题，例如$ 1 || \ sum w_ju_j $，最小化单台计算机上迟来作业的总重量的问题以及$ p_2 || \ sum u_j $，这是最小化两台相同平行机器上迟来作业数量的问题。
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-ε})$, for $t_{max}=\max_i t_i$ and any $ε> 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-ε})$-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.
