Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.4
URN: urn:nbn:de:0030-drops-124119
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12411/
Abboud, Amir ; Bringmann, Karl ; Hermelin, Danny ; Shabtay, Dvir
Scheduling Lower Bounds via AND Subset Sum
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{abboud_et_al:LIPIcs:2020:12411,
author = {Amir Abboud and Karl Bringmann and Danny Hermelin and Dvir Shabtay},
title = {{Scheduling Lower Bounds via AND Subset Sum}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {4:1--4:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-138-2},
ISSN = {1868-8969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12411},
URN = {urn:nbn:de:0030-drops-124119},
doi = {10.4230/LIPIcs.ICALP.2020.4},
annote = {Keywords: SETH, fine grained complexity, Subset Sum, scheduling}
}
| Keywords: | SETH, fine grained complexity, Subset Sum, scheduling | |
| Seminar: | 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 29.06.2020 |
