@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",
}