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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

12 Citations (Scopus)

40 Downloads (Pure)

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^∗(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.

Original language	English
Title of host publication	27th Annual European Symposium on Algorithms, ESA 2019
Editors	Michael A. Bender, Ola Svensson, Grzegorz Herman
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages	16
ISBN (Electronic)	978-3-95977-124-5
DOIs	https://doi.org/10.4230/LIPIcs.ESA.2019.73
Publication status	Published - Sept 2019
Event	27th Annual European Symposium on Algorithms, ESA 2019 - Munich/Garching, Germany Duration: 9 Sept 2019 → 11 Sept 2019

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	144
ISSN (Print)	1868-8969

Conference

Conference	27th Annual European Symposium on Algorithms, ESA 2019
Country/Territory	Germany
City	Munich/Garching
Period	9/09/19 → 11/09/19

Funding

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

Keywords

Enumeration technique
Equal-Subset-Sum
Meet-in-the-middle
Randomized algorithm
Subset-Sum
meet-in-the-middle
randomized algorithm
enumeration technique

Access to Document

10.4230/LIPIcs.ESA.2019.73

published versionFinal published version, 525 KB

Cite this

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 (Eds.), 27th Annual European Symposium on Algorithms, ESA 2019 Article 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 (eds), 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, Germany, 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. ed. / Michael A. Bender; Ola Svensson; Grzegorz Herman. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. 73 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 144).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › 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 - http://www.scopus.com/inward/record.url?scp=85074847797&partnerID=8YFLogxK

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

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this