Revisiting the Random Subset Sum problem

MaRDI QIDQ6507820arXivFDO

Authors Arthur L. da Cunha, Francesco d'Amore, F. Giroire, Hicham Lesfari, Emanuele Natale, Laurent Viennot

Published in arXiv

Abstract: 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 $X_1,ldots,X_n$, and an error parameter $varepsilon>0$, and we seek a subset of the $X_i$s whose sum approximates $z$ up to error $varepsilon$. In this setup, it has been shown that, under mild assumptions on the distribution of the random variables, a sample of size $mathcalO(log(1/varepsilon))$ 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.

This page was built for publication: Revisiting the Random Subset Sum problem

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