Dense subset sum may be the hardest

DOI10.4230/LIPICS.STACS.2016.13MaRDI QIDQ4601865zbMATH OpenFDO

Authors Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper Nederlof

Publication date 24 January 2018

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

zbMATH Keywords

additive combinatoricsexponential-time algorithmhomomorphic hashingLittlewood-Offord problemsubset sum

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics in computer science (68R05) Analysis of algorithms (68W40)

Abstract: The Subset Sum problem asks whether a given set of $n$ positive integers contains a subset of elements that sum up to a given target $t$. It is an outstanding open question whether the $O^{\ast }(2^{n/2})$-time algorithm for Subset Sum by Horowitz and Sahni [J. ACM 1974] can be beaten in the worst-case setting by a "truly faster", $O^{\ast }(2^{(0.5-delta)n})$-time algorithm, with some constant $delta>0$. Continuing an earlier work [STACS 2015], we study Subset Sum parameterized by the maximum bin size $$, defined as the largest number of subsets of the $n$ input integers that yield the same sum. For every $epsilon>0$ we give a truly faster algorithm for instances with $$, as well as instances with $$. Consequently, we also obtain a characterization in terms of the popular density parameter $n/lo{g}_{2}t$: if all instances of density at least $1.003$ admit a truly faster algorithm, then so does every instance. This goes against the current intuition that instances of density 1 are the hardest, and therefore is a step toward answering the open question in the affirmative. Our results stem from novel combinations of earlier algorithms for Subset Sum and a study of an extremal question in additive combinatorics connected to the problem of Uniquely Decodable Code Pairs in information theory.

Recommendations

• STACS 2005
• An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem
• scientific article; zbMATH DE number 176777
• An Improved Low-Density Subset Sum Algorithm
• Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach

Cited in

(17)

• Approximating subset sum ratio via subset sum computations
• Subset sum in the absence of concentration
• A short note on Merlin-Arthur protocols for subset sum
• Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems
• Equal-subset-sum faster than the meet-in-the-middle
• Anticoncentration versus the Number of Subset Sums
• SETH-based lower bounds for subset sum and bicriteria path
• STACS 2005
• SETH-based Lower Bounds for Subset Sum and Bicriteria Path
• A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
• Improved Merlin-Arthur protocols for central problems in fine-grained complexity
• Approximating subset sum ratio via partition computations
• A faster algorithm for pigeonhole equal sums
• Fast n-fold Boolean convolution via additive combinatorics
• Parameterized algorithms on integer sets with small doubling: integer programming, subset sum and k-SUM
• Does subset sum admit short proofs?
• New algorithms for pigeonhole equal subset sum

This page was built for publication: Dense subset sum may be the hardest

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601865)