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

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

5 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(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.

Originele taal-2Engels
Titel27th Annual European Symposium on Algorithms, ESA 2019
RedacteurenMichael A. Bender, Ola Svensson, Grzegorz Herman
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Aantal pagina's16
ISBN van elektronische versie978-3-95977-124-5
DOI's
StatusGepubliceerd - sep 2019
Evenement27th Annual European Symposium on Algorithms, ESA 2019 - Munich/Garching, Duitsland
Duur: 9 sep 201911 sep 2019

Publicatie series

NaamLeibniz International Proceedings in Informatics, LIPIcs
Volume144
ISSN van geprinte versie1868-8969

Congres

Congres27th Annual European Symposium on Algorithms, ESA 2019
LandDuitsland
StadMunich/Garching
Periode9/09/1911/09/19

Vingerafdruk Duik in de onderzoeksthema's van 'Equal-subset-sum faster than the meet-in-the-middle'. Samen vormen ze een unieke vingerafdruk.

  • 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 [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