Equal-Subset-Sum Faster Than the Meet-in-the-Middle

2019/05/07 by Mucha, Marcin, Nederlof, Jesper, Pawlewicz, Jakub +1 · 1 citation
#Data Structures and Algorithms (cs.DS) #F.2 #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1905.02424

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/2) ≤ 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 the open problem from Woeginger's 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.

Cited by

• Beating Meet-in-the-Middle for Subset Balancing Problems

Related

• Average-Case Subset Balancing Problems
• Faster Space-Efficient Algorithms for Subset Sum, k-Sum and Related\n Problems
• The problematic nature of potentially polynomial-time algorithms solving the subset-sum problem
• A novel and efficient algorithm to solve subset sum problem
• Dense Subset Sum may be the hardest