# Scheduling Lower Bounds via AND Subset Sum

arXiv: https://arxiv.org/abs/2003.07113 · HTML: https://mlsanity.com/paper/2003.07113/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Mar 2020.

## Built on by (most cited first, 1 of 1)

- [On Complexity of 1-Center in Various Metrics](https://mlsanity.com/paper/2112.03222/) (2021)

## Abstract (arXiv)

Given N instances (X1,t1),ldots,(XN,tN) 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 Xi has a subset that sums up to the target integer ti. We prove that this problem cannot be solved in time tildeO((N · tmax)1-ε), for tmax=maxi ti and any ε > 0, assuming the forall exists Strong Exponential Time Hypothesis (forall exists-SETH). We then use this result to exclude tildeO(n+Pmax · n1-ε)-time algorithms for several scheduling problems on n jobs with maximum processing time Pmax, based on forall exists-SETH. These include classical problems such as 1||sum wjUj, the problem of minimizing the total weight of tardy jobs on a single machine, and P2||sum Uj, the problem of minimizing the number of tardy jobs on two identical parallel machines.