2026-08-02T03:32:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12411 2024-03-06T10:50:04Z ddc:004 open_access

Scheduling Lower Bounds via AND Subset Sum Abboud, Amir Bringmann, Karl Hermelin, Danny Shabtay, Dvir SETH fine grained complexity Subset Sum scheduling Given N instances (X_1,t_1),…,(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 Õ((N ⋅ t_max)^{1-ε}), for t_max = max_i t_i and any ε > 0, assuming the ∀ ∃ Strong Exponential Time Hypothesis (∀∃-SETH). We then use this result to exclude Õ(n+P_max⋅n^{1-ε})-time algorithms for several scheduling problems on n jobs with maximum processing time P_max, assuming ∀∃-SETH. These include classical problems such as 1||∑ w_jU_j, the problem of minimizing the total weight of tardy jobs on a single machine, and P₂||∑ U_j, the problem of minimizing the number of tardy jobs on two identical parallel machines. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amir Abboud and Karl Bringmann and Danny Hermelin and Dvir Shabtay 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.4 urn:nbn:de:0030-drops-124119 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.4 eng https://creativecommons.org/licenses/by/3.0/legalcode