日本語
 
Help Privacy Policy ポリシー/免責事項
  詳細検索ブラウズ

アイテム詳細


公開

成果報告書

Scheduling Lower Bounds via AND Subset Sum

MPS-Authors
/persons/resource/persons44182

Bringmann,  Karl       
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
There are no locators available
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
フルテキスト (公開)

arXiv:2003.07113.pdf
(プレプリント), 238KB

付随資料 (公開)
There is no public supplementary material available
引用

Abboud, A., Bringmann, K., Hermelin, D., & Shabtay, D. (2020). Scheduling Lower Bounds via AND Subset Sum. Retrieved from https://arxiv.org/abs/2003.07113.


引用: https://hdl.handle.net/21.11116/0000-0007-2A52-E
要旨
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.