AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

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 of 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 exponentially many random bits, we show a randomized algorithm running in O(2.6817^n) time and polynomial space.

Joint work with Marcin Mucha, Jesper Nederlof and Jakub Pawlewicz.

Karl Bringmann

--email hidden

passcode not visible

logged in users only