Pigeonhole Equal Subset Sum in O ⃰ (2ⁿ/³)

Subset Sum is a well known NP-hard problem. In Subset Sum, we are given a set of n integers S = {a1,··· ,an} and a target integer t, and are asked to find a subset A ⊆ [n] such that [formula]. We study a variant of the Subset Sum problem, Pigeonhole Equal Subset Sum. In Pigeonhole Equal Subset Sum, we are given a set of n integers S ={a₁,··· , aₙ} with the additional restriction that [formula], and want to find two different subsets A,B ⊆ [n] such that [formula]. The naive algorithm where we enumerate over all subset sums and look for a match takes O∗(2ⁿ) time. Horowitz and Sahni improve this to O ⃰ (2ⁿ/²) using a classical meet in the middle algorithm [1]. Recently, Jin and Wu improved this further to [formula] [2]. In this paper, we build on Jin and Wu’s techniques to improve the runtime even further to O ⃰ (2ⁿ/³).

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2024

Author dc:creator

• Zhang, Stan

Advisor dc:contributor.advisor

• Williams, Ryan

Statement dc:rights

• Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)
• Copyright retained by author(s)

Licence dc:rights.uri

• https://creativecommons.org/licenses/by-nc-nd/4.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/156830

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/156830