English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

On Near-Linear-Time Algorithms for Dense Subset Sum

MPS-Authors
/persons/resource/persons44182

Bringmann,  Karl
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons229250

Wellnitz,  Philip
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)

arXiv:2010.09096.pdf
(Preprint), 843KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Bringmann, K., & Wellnitz, P. (2020). On Near-Linear-Time Algorithms for Dense Subset Sum. Retrieved from https://arxiv.org/abs/2010.09096.


Cite as: http://hdl.handle.net/21.11116/0000-0007-8C97-1
Abstract
In the Subset Sum problem we are given a set of $n$ positive integers $X$ and a target $t$ and are asked whether some subset of $X$ sums to $t$. Natural parameters for this problem that have been studied in the literature are $n$ and $t$ as well as the maximum input number $\rm{mx}_X$ and the sum of all input numbers $\Sigma_X$. In this paper we study the dense case of Subset Sum, where all these parameters are polynomial in $n$. In this regime, standard pseudo-polynomial algorithms solve Subset Sum in polynomial time $n^{O(1)}$. Our main question is: When can dense Subset Sum be solved in near-linear time $\tilde{O}(n)$? We provide an essentially complete dichotomy by designing improved algorithms and proving conditional lower bounds, thereby determining essentially all settings of the parameters $n,t,\rm{mx}_X,\Sigma_X$ for which dense Subset Sum is in time $\tilde{O}(n)$. For notational convenience we assume without loss of generality that $t \ge \rm{mx}_X$ (as larger numbers can be ignored) and $t \le \Sigma_X/2$ (using symmetry). Then our dichotomy reads as follows: - By reviving and improving an additive-combinatorics-based approach by Galil and Margalit [SICOMP'91], we show that Subset Sum is in near-linear time $\tilde{O}(n)$ if $t \gg \rm{mx}_X \Sigma_X/n^2$. - We prove a matching conditional lower bound: If Subset Sum is in near-linear time for any setting with $t \ll \rm{mx}_X \Sigma_X/n^2$, then the Strong Exponential Time Hypothesis and the Strong k-Sum Hypothesis fail. We also generalize our algorithm from sets to multi-sets, albeit with non-matching upper and lower bounds.