Revisiting the Random Subset Sum Problem

Arthur da Cunha; Francesco d'Amore; Frédéric Giroire; Hicham Lesfari; Emanuele Natale; Laurent Viennot

doi:10.4230/LIPIcs.ESA.2023.37

Revisiting the Random Subset Sum Problem

Arthur da Cunha, Francesco d'Amore, Frédéric Giroire, Hicham Lesfari, Emanuele Natale, Laurent Viennot

Department of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

2 Citations (Scopus)

185 Downloads (Pure)

Abstract

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.

Original language	English
Title of host publication	31st Annual European Symposium on Algorithms (ESA 2023)
Editors	Inge Li Gortz, Martin Farach-Colton, Simon J. Puglisi, Grzegorz Herman
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	1-11
Number of pages	11
ISBN (Electronic)	978-3-95977-295-2
DOIs	https://doi.org/10.4230/LIPIcs.ESA.2023.37
Publication status	Published - 30 Aug 2023
MoE publication type	A4 Conference publication
Event	European Symposium on Algorithms - Amsterdam, Netherlands Duration: 4 Sept 2023 → 6 Sept 2023 Conference number: 31

Publication series

Name	Leibniz International Proceedings in Informatics (LIPIcs)
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Volume	274
ISSN (Electronic)	1868-8969

Conference

Conference	European Symposium on Algorithms
Abbreviated title	ESA
Country/Territory	Netherlands
City	Amsterdam
Period	04/09/2023 → 06/09/2023

Keywords

Random subset sum
Randomised method
Subset-sum
Combinatorics

Access to Document

10.4230/LIPIcs.ESA.2023.37Licence: CC BY

Revisiting the Random Subset Sum ProblemFinal published version, 696 KBLicence: CC BY

Cite this

da Cunha, A., d'Amore, F., Giroire, F., Lesfari, H., Natale, E., & Viennot, L. (2023). Revisiting the Random Subset Sum Problem. In I. Li Gortz, M. Farach-Colton, S. J. Puglisi, & G. Herman (Eds.), 31st Annual European Symposium on Algorithms (ESA 2023) (pp. 1-11). Article 37 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 274). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2023.37

da Cunha, Arthur ; d'Amore, Francesco ; Giroire, Frédéric et al. / Revisiting the Random Subset Sum Problem. 31st Annual European Symposium on Algorithms (ESA 2023). editor / Inge Li Gortz ; Martin Farach-Colton ; Simon J. Puglisi ; Grzegorz Herman. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. pp. 1-11 (Leibniz International Proceedings in Informatics (LIPIcs)).

@inproceedings{58756f7d78f6497f872c4a1cb1ffca1d,

title = "Revisiting the Random Subset Sum Problem",

abstract = "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. ",

keywords = "Random subset sum, Randomised method, Subset-sum, Combinatorics",

author = "{da Cunha}, Arthur and Francesco d'Amore and Fr{\'e}d{\'e}ric Giroire and Hicham Lesfari and Emanuele Natale and Laurent Viennot",

year = "2023",

month = aug,

day = "30",

doi = "10.4230/LIPIcs.ESA.2023.37",

language = "English",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "1--11",

editor = "{Li Gortz}, Inge and Martin Farach-Colton and Puglisi, {Simon J.} and Grzegorz Herman",

booktitle = "31st Annual European Symposium on Algorithms (ESA 2023)",

address = "Germany",

note = "European Symposium on Algorithms, ESA ; Conference date: 04-09-2023 Through 06-09-2023",

}

da Cunha, A, d'Amore, F, Giroire, F, Lesfari, H, Natale, E & Viennot, L 2023, Revisiting the Random Subset Sum Problem. in I Li Gortz, M Farach-Colton, SJ Puglisi & G Herman (eds), 31st Annual European Symposium on Algorithms (ESA 2023)., 37, Leibniz International Proceedings in Informatics (LIPIcs), vol. 274, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-11, European Symposium on Algorithms, Amsterdam, Netherlands, 04/09/2023. https://doi.org/10.4230/LIPIcs.ESA.2023.37

Revisiting the Random Subset Sum Problem. / da Cunha, Arthur; d'Amore, Francesco; Giroire, Frédéric et al.
31st Annual European Symposium on Algorithms (ESA 2023). ed. / Inge Li Gortz; Martin Farach-Colton; Simon J. Puglisi; Grzegorz Herman. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. p. 1-11 37 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 274).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

T1 - Revisiting the Random Subset Sum Problem

AU - da Cunha, Arthur

AU - d'Amore, Francesco

AU - Giroire, Frédéric

AU - Lesfari, Hicham

AU - Natale, Emanuele

AU - Viennot, Laurent

N1 - Conference code: 31

PY - 2023/8/30

Y1 - 2023/8/30

N2 - 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.

AB - 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.

KW - Random subset sum

KW - Randomised method

KW - Subset-sum

KW - Combinatorics

UR - http://www.scopus.com/inward/record.url?scp=85173450679&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ESA.2023.37

DO - 10.4230/LIPIcs.ESA.2023.37

M3 - Conference article in proceedings

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 1

EP - 11

BT - 31st Annual European Symposium on Algorithms (ESA 2023)

A2 - Li Gortz, Inge

A2 - Farach-Colton, Martin

A2 - Puglisi, Simon J.

A2 - Herman, Grzegorz

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - European Symposium on Algorithms

Y2 - 4 September 2023 through 6 September 2023

ER -

da Cunha A, d'Amore F, Giroire F, Lesfari H, Natale E, Viennot L. Revisiting the Random Subset Sum Problem. In Li Gortz I, Farach-Colton M, Puglisi SJ, Herman G, editors, 31st Annual European Symposium on Algorithms (ESA 2023). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2023. p. 1-11. 37. (Leibniz International Proceedings in Informatics (LIPIcs)). doi: 10.4230/LIPIcs.ESA.2023.37

Revisiting the Random Subset Sum Problem

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this