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 proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)
16 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(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.

Original languageEnglish
Title of host publication27th Annual European Symposium on Algorithms, ESA 2019
EditorsMichael A. Bender, Ola Svensson, Grzegorz Herman
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages16
ISBN (Electronic)978-3-95977-124-5
DOIs
Publication statusPublished - Sep 2019
Event27th Annual European Symposium on Algorithms, ESA 2019 - Munich/Garching, Germany
Duration: 9 Sep 201911 Sep 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume144
ISSN (Print)1868-8969

Conference

Conference27th Annual European Symposium on Algorithms, ESA 2019
Country/TerritoryGermany
CityMunich/Garching
Period9/09/1911/09/19

Keywords

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

Fingerprint

Dive into the research topics of 'Equal-subset-sum faster than the meet-in-the-middle'. Together they form a unique fingerprint.

Cite this