Scheduling lower bounds via AND subset sum

Abboud, 2019, SETH-based lower bounds for subset sum and bicriteria path, 41 Abboud, 2016, Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs, 377 Ancona Axiotis, 2019, Fast modular subset sum using linear sketching, 58 Behrend, 1946, On sets of integers which contain no three terms in arithmetical progression, Proc. Natl. Acad. Sci. USA, 32, 331, 10.1073/pnas.32.12.331 Bellman, 1957 Bringmann, 2017, A near-linear pseudopolynomial time algorithm for subset sum, 1073 Bringmann, 2019, Polyline simplification has cubic complexity, 18:1 Brucker, 2006 Carmosino, 2016, Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility, 261 Cheng, 2016, An alternative approach for proving the NP-hardness of optimization problems, Eur. J. Oper. Res., 248, 52, 10.1016/j.ejor.2015.06.076 Cygan, 2016, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström. On problems as hard as CNF-SAT, ACM Trans. Algorithms, 12, 41, 10.1145/2925416 Demaine Dolev, 1985, Profile scheduling of opposing forests and level orders, SIAM J. Algebraic Discrete Methods, 6, 665, 10.1137/0606066 Du, 1990, Minimizing total tardiness on one machine is NP-hard, Math. Oper. Res., 15, 483, 10.1287/moor.15.3.483 Eisenbrand, 2018, Proximity results and faster algorithms for integer programming using the steinitz lemma, 808 Galil, 1991, An almost linear-time algorithm for the dense subset-sum problem, SIAM J. Comput., 20, 1157, 10.1137/0220072 Gao, 2018, Completeness for first-order properties on sparse structures with algorithmic applications, ACM Trans. Algorithms, 15, 1, 10.1145/3196275 Garroppo, 2010, A survey on multi-constrained optimal path computation: exact and approximate algorithms, Comput. Netw., 54, 3081, 10.1016/j.comnet.2010.05.017 Graham, 1979, Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math., 5, 287, 10.1016/S0167-5060(08)70356-X Impagliazzo, 1996, Efficient cryptographic schemes provably as secure as subset sum, J. Cryptol., 9, 199, 10.1007/BF00189260 Impagliazzo, 2001, On the complexity of k-SAT, J. Comput. Syst. Sci., 62, 367, 10.1006/jcss.2000.1727 Impagliazzo, 2001, Which problems have strongly exponential complexity?, J. Comput. Syst. Sci., 63, 512, 10.1006/jcss.2001.1774 Jin, 2018, A simple near-linear pseudopolynomial time randomized algorithm for subset sum, 17:1 Karp, 1972, Reducibility among combinatorial problems, 85 Khowala, 2008, A comparison of different formulations for the non-preemptive single machine total weighted tardiness scheduling problem Koiliaris, 2019, A faster pseudopolynomial time algorithm for subset sum, ACM Trans. Algorithms, 15, 40:1, 10.1145/3329863 Kovalyov, 2010, A generic approach to proving NP-hardness of partition type problems, Discrete Appl. Math., 158, 1908, 10.1016/j.dam.2010.08.001 Lawler, 1969, A functional equation and its application to resource allocation and sequencing problems, Manag. Sci., 16, 77, 10.1287/mnsc.16.1.77 Merkle, 1978, Hiding information and signatures in trapdoor knapsacks, IEEE Trans. Inf. Theory, 24, 525, 10.1109/TIT.1978.1055927 Pan, 2007, On the equivalence of the max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems, Math. Program., 110, 543, 10.1007/s10107-006-0013-4 Pinedo, 2008 Pisinger, 1999, Linear time algorithms for knapsack problems with bounded weights, J. Algorithms, 32, 1, 10.1006/jagm.1999.1034 Ragatz, 1993, A branch-and-bound method for minimum tardiness sequencing on a single processor with sequence dependent setup times, 1375 Rohatgi Rothkopf, 1966, Scheduling independent tasks on parallel processors, Manag. Sci., 12, 437, 10.1287/mnsc.12.5.437 Santhanam, 2014, Beating exhaustive search for quantified boolean formulas and connections to circuit complexity, 231 Shabtay, 2013, A survey on offline scheduling with rejection, J. Sched., 16, 3, 10.1007/s10951-012-0303-z Voinov, 1997, 153 Wang, 2019, The complexity of parallel machine scheduling of unit-processing-time jobs under level-order precedence constraints, J. Sched., 263, 10.1007/s10951-018-0596-7 Williams, 2005, A new algorithm for optimal 2-constraint satisfaction and its implications, Theor. Comput. Sci., 348, 357, 10.1016/j.tcs.2005.09.023 Younis, 2003, Constraint-based routing in the internet: basic principles and recent research, IEEE Commun. Surv. Tutor., 5, 2, 10.1109/COMST.2003.5342226