2026-07-20T10:52:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18690 2024-03-06T11:02:28Z ddc:004 open_access

Revisiting the Random Subset Sum Problem Da Cunha, Arthur Carvalho Walraven d'Amore, Francesco Giroire, Frédéric Lesfari, Hicham Natale, Emanuele Viennot, Laurent Random subset sum Randomised method Subset-sum Combinatorics The average properties of the well-known Subset Sum Problem can be studied by means of its randomised version, where we are given a target value z, random variables X_1, …, X_n, and an error parameter ε > 0, and we seek a subset of the X_is 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 𝒪(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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arthur Carvalho Walraven Da Cunha and Francesco d'Amore and Frédéric Giroire and Hicham Lesfari and Emanuele Natale and Laurent Viennot 2023 Is Part Of LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2023.37 urn:nbn:de:0030-drops-186905 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.37 eng https://creativecommons.org/licenses/by/4.0/legalcode