Equal-subset-sum faster than the meet-in-the-middle

Marcin Mucha; Jesper Nederlof; Jakub Pawlewicz; Karol Węgrzycki

doi:10.4230/LIPIcs.ESA.2019.73

Equal-subset-sum faster than the meet-in-the-middle

Marcin Mucha
, Jesper Nederlof
, Jakub Pawlewicz
, Karol Węgrzycki

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

14 Citaten (Scopus)

99 Downloads (Pure)

Samenvatting

In the Equal-Subset-Sum problem, we are given a set S of n integers and the problem is to decide if there exist two disjoint nonempty subsets A, B ⊆ S, whose elements sum up to the same value. The problem is NP-complete. The state-of-the-art algorithm runs in O^∗(3^n/²) ≤ O^∗(1.7321ⁿ) time and is based on the meet-in-the-middle technique. In this paper, we improve upon this algorithm and give O^∗(1.7088ⁿ) worst case Monte Carlo algorithm. This answers a question suggested by Woeginger in his inspirational survey. Additionally, we analyse the polynomial space algorithm for Equal-Subset-Sum. A naive polynomial space algorithm for Equal-Subset-Sum runs in O^∗(3ⁿ) time. With read-only access to the exponentially many random bits, we show a randomized algorithm running in O^∗(2.6817ⁿ) time and polynomial space.

Originele taal-2	Engels
Titel	27th Annual European Symposium on Algorithms, ESA 2019
Redacteuren	Michael A. Bender, Ola Svensson, Grzegorz Herman
Uitgeverij	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Aantal pagina's	16
ISBN van elektronische versie	978-3-95977-124-5
DOI's	https://doi.org/10.4230/LIPIcs.ESA.2019.73
Status	Gepubliceerd - sep. 2019
Evenement	27th Annual European Symposium on Algorithms, ESA 2019 - Munich/Garching, Duitsland Duur: 9 sep. 2019 → 11 sep. 2019

Publicatie series

Naam	Leibniz International Proceedings in Informatics, LIPIcs
Volume	144
ISSN van geprinte versie	1868-8969

Congres

Congres	27th Annual European Symposium on Algorithms, ESA 2019
Land/Regio	Duitsland
Stad	Munich/Garching
Periode	9/09/19 → 11/09/19

Financiering

Funding Marcin Mucha: Supported by project TOTAL that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 677651). Jesper Nederlof : Supported by the Netherlands Organization for Scientific Research under project no. 024.002.003 and the European Research Council under project no. 617951. Karol Węgrzycki: Supported by the grants 2016/21/N/ST6/01468 and 2018/28/T/ST6/00084 of the Polish National Science Center and project TOTAL that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 677651).

Toegang tot document

10.4230/LIPIcs.ESA.2019.73

published versionDefinitieve gepubliceerde versie, 525 KB

Andere bestanden en links

Link to publication in Scopus

Citeer dit

Mucha, M., Nederlof, J., Pawlewicz, J., & Węgrzycki, K. (2019). Equal-subset-sum faster than the meet-in-the-middle. In M. A. Bender, O. Svensson, & G. Herman (editors), 27th Annual European Symposium on Algorithms, ESA 2019 Artikel 73 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 144). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2019.73

@inproceedings{531ed6e5b1494da787a1a737d0a5f827,

title = "Equal-subset-sum faster than the meet-in-the-middle",

abstract = "In the Equal-Subset-Sum problem, we are given a set S of n integers and the problem is to decide if there exist two disjoint nonempty subsets A, B ⊆ S, whose elements sum up to the same value. The problem is NP-complete. The state-of-the-art algorithm runs in O∗(3n/2) ≤ O∗(1.7321n) time and is based on the meet-in-the-middle technique. In this paper, we improve upon this algorithm and give O∗(1.7088n) worst case Monte Carlo algorithm. This answers a question suggested by Woeginger in his inspirational survey. Additionally, we analyse the polynomial space algorithm for Equal-Subset-Sum. A naive polynomial space algorithm for Equal-Subset-Sum runs in O∗(3n) time. With read-only access to the exponentially many random bits, we show a randomized algorithm running in O∗(2.6817n) time and polynomial space.",

keywords = "Enumeration technique, Equal-Subset-Sum, Meet-in-the-middle, Randomized algorithm, Subset-Sum, meet-in-the-middle, randomized algorithm, enumeration technique",

author = "Marcin Mucha and Jesper Nederlof and Jakub Pawlewicz and Karol W{\c e}grzycki",

year = "2019",

month = sep,

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

language = "English",

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

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

editor = "Bender, \{Michael A.\} and Ola Svensson and Grzegorz Herman",

booktitle = "27th Annual European Symposium on Algorithms, ESA 2019",

note = "27th Annual European Symposium on Algorithms, ESA 2019 ; Conference date: 09-09-2019 Through 11-09-2019",

}

Mucha, M, Nederlof, J, Pawlewicz, J & Węgrzycki, K 2019, Equal-subset-sum faster than the meet-in-the-middle. in MA Bender, O Svensson & G Herman (reds.), 27th Annual European Symposium on Algorithms, ESA 2019., 73, Leibniz International Proceedings in Informatics, LIPIcs, vol. 144, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 27th Annual European Symposium on Algorithms, ESA 2019, Munich/Garching, Duitsland, 9/09/19. https://doi.org/10.4230/LIPIcs.ESA.2019.73

Equal-subset-sum faster than the meet-in-the-middle. / Mucha, Marcin; Nederlof, Jesper; Pawlewicz, Jakub et al.
27th Annual European Symposium on Algorithms, ESA 2019. reds. / Michael A. Bender; Ola Svensson; Grzegorz Herman. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. 73 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 144).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

TY - GEN

T1 - Equal-subset-sum faster than the meet-in-the-middle

AU - Mucha, Marcin

AU - Nederlof, Jesper

AU - Pawlewicz, Jakub

AU - Węgrzycki, Karol

PY - 2019/9

Y1 - 2019/9

N2 - In the Equal-Subset-Sum problem, we are given a set S of n integers and the problem is to decide if there exist two disjoint nonempty subsets A, B ⊆ S, whose elements sum up to the same value. The problem is NP-complete. The state-of-the-art algorithm runs in O∗(3n/2) ≤ O∗(1.7321n) time and is based on the meet-in-the-middle technique. In this paper, we improve upon this algorithm and give O∗(1.7088n) worst case Monte Carlo algorithm. This answers a question suggested by Woeginger in his inspirational survey. Additionally, we analyse the polynomial space algorithm for Equal-Subset-Sum. A naive polynomial space algorithm for Equal-Subset-Sum runs in O∗(3n) time. With read-only access to the exponentially many random bits, we show a randomized algorithm running in O∗(2.6817n) time and polynomial space.

AB - In the Equal-Subset-Sum problem, we are given a set S of n integers and the problem is to decide if there exist two disjoint nonempty subsets A, B ⊆ S, whose elements sum up to the same value. The problem is NP-complete. The state-of-the-art algorithm runs in O∗(3n/2) ≤ O∗(1.7321n) time and is based on the meet-in-the-middle technique. In this paper, we improve upon this algorithm and give O∗(1.7088n) worst case Monte Carlo algorithm. This answers a question suggested by Woeginger in his inspirational survey. Additionally, we analyse the polynomial space algorithm for Equal-Subset-Sum. A naive polynomial space algorithm for Equal-Subset-Sum runs in O∗(3n) time. With read-only access to the exponentially many random bits, we show a randomized algorithm running in O∗(2.6817n) time and polynomial space.

KW - Enumeration technique

KW - Equal-Subset-Sum

KW - Meet-in-the-middle

KW - Randomized algorithm

KW - Subset-Sum

KW - meet-in-the-middle

KW - randomized algorithm

KW - enumeration technique

UR - https://www.scopus.com/pages/publications/85074847797

U2 - 10.4230/LIPIcs.ESA.2019.73

DO - 10.4230/LIPIcs.ESA.2019.73

M3 - Conference contribution

AN - SCOPUS:85074847797

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 27th Annual European Symposium on Algorithms, ESA 2019

A2 - Bender, Michael A.

A2 - Svensson, Ola

A2 - Herman, Grzegorz

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

T2 - 27th Annual European Symposium on Algorithms, ESA 2019

Y2 - 9 September 2019 through 11 September 2019

ER -

Equal-subset-sum faster than the meet-in-the-middle

Samenvatting

Publicatie series

Congres

Financiering

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit