Revisiting the Random Subset Sum problem
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909126161858560 |
|---|---|
| author | da Cunha, Arthur d'Amore, Francesco Giroire, Frédéric Lesfari, Hicham Natale, Emanuele Viennot, Laurent |
| author_facet | da Cunha, Arthur d'Amore, Francesco Giroire, Frédéric Lesfari, Hicham Natale, Emanuele Viennot, Laurent |
| contents | 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 $\mathcal{O}(\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2204_13929 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Revisiting the Random Subset Sum problem da Cunha, Arthur d'Amore, Francesco Giroire, Frédéric Lesfari, Hicham Natale, Emanuele Viennot, Laurent Probability Combinatorics 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 $\mathcal{O}(\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. |
| title | Revisiting the Random Subset Sum problem |
| topic | Probability Combinatorics |
| url | https://arxiv.org/abs/2204.13929 |