2022/04/29 by da Cunha, Arthur, d'Amore, Francesco, Giroire, Frédéric +3
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2204.13929
The average properties of the well-known Subset Sum Problem can be studied by the means of its randomised version, where we are given a target value z, random variables X1, …, Xn, and an error parameter ε > 0, and we seek a subset of the Xis whose sum approximates z up to error ε. In this setup, it has been shown that, under mild assumptions on the distribution of the random variables, a sample of size O(log(1/ε)) suffices to obtain, with high probability, approximations for all values in [-1/2, 1/2]. Recently, this result has been rediscovered outside the algorithms community, enabling meaningful progress in other fields. In this work we present an alternative proof for this theorem, with a more direct approach and resourcing to more elementary tools.