Scheduling lower bounds via AND subset sum
From MaRDI portal
Publication:2121467
DOI10.1016/j.jcss.2022.01.005zbMath1483.68142arXiv2003.07113OpenAlexW4211178172MaRDI QIDQ2121467
Dvir Shabtay, Amir Abboud, Danny Hermelin, Karl Bringmann
Publication date: 4 April 2022
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2003.07113
Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (1)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An alternative approach for proving the NP-hardness of optimization problems
- A survey on offline scheduling with rejection
- A generic approach to proving NP-hardness of partition type problems
- A survey on multi-constrained optimal path computation: exact and approximate algorithms
- On the equivalence of the Max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems
- Which problems have strongly exponential complexity?
- The complexity of parallel machine scheduling of unit-processing-time jobs under level-order precedence constraints
- Off-diagonal ordered Ramsey numbers of matchings
- Efficient cryptographic schemes provably as secure as subset sum
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
- Minimizing Total Tardiness on One Machine is NP-Hard
- Profile Scheduling of Opposing Forests and Level Orders
- An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
- Completeness for First-order Properties on Sparse Structures with Algorithmic Applications
- Linear Time Algorithms for Knapsack Problems with Bounded Weights
- On Problems as Hard as CNF-SAT
- Faster Pseudopolynomial Time Algorithms for Subset Sum
- Reducibility among Combinatorial Problems
- SETH-Based Lower Bounds for Subset Sum and Bicriteria Path
- Fast Modular Subset Sum using Linear Sketching
- Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity
- A Functional Equation and its Application to Resource Allocation and Sequencing Problems
- On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
- Polyline simplification has cubic complexity
- Hiding information and signatures in trapdoor knapsacks
- Scheduling
- On the complexity of \(k\)-SAT
This page was built for publication: Scheduling lower bounds via AND subset sum
