SETH-Based Lower Bounds for Subset Sum and Bicriteria Path

DOI10.1137/1.9781611975482.3zbMath1431.68040arXiv1704.04546OpenAlexW2951283560MaRDI QIDQ5236184

Dvir Shabtay, Karl Bringmann, Danny Hermelin, Amir Abboud

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1704.04546

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (15)

Scheduling lower bounds via AND subset sum ⋮ Faster minimization of tardy processing time on a single machine ⋮ Approximating subset sum ratio via subset sum computations ⋮ Algebraic algorithms for variants of subset sum ⋮ On the complexity of scheduling problems with a fixed number of parallel identical machines ⋮ The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Faster Pseudopolynomial Time Algorithms for Subset Sum ⋮ Low weight discrete logarithm and subset sum in \(2^{0.65n}\) with polynomial memory ⋮ On Integer Programming and Convolution. ⋮ Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. ⋮ Fine-Grained Complexity Theory (Tutorial) ⋮ Quantum Hardness of Learning Shallow Classical Circuits

This page was built for publication: SETH-Based Lower Bounds for Subset Sum and Bicriteria Path