2026-07-21T12:57:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11194 2024-03-06T10:47:41Z ddc:004 open_access

Equal-Subset-Sum Faster Than the Meet-in-the-Middle Mucha, Marcin Nederlof, Jesper Pawlewicz, Jakub Węgrzycki, Karol Equal-Subset-Sum Subset-Sum meet-in-the-middle enumeration technique randomized algorithm 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 subseteq 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/2)) <= O^*(1.7321^n) time and is based on the meet-in-the-middle technique. In this paper, we improve upon this algorithm and give O^*(1.7088^n) 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^n) time. With read-only access to the exponentially many random bits, we show a randomized algorithm running in O^*(2.6817^n) time and polynomial space. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marcin Mucha and Jesper Nederlof and Jakub Pawlewicz and Karol Węgrzycki 2019 Is Part Of LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2019.73 urn:nbn:de:0030-drops-111946 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.73 eng https://creativecommons.org/licenses/by/3.0/legalcode