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,...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2024
|
| Online Access: | https://hdl.handle.net/1721.1/156830 |
| _version_ | 1811094429686038528 |
|---|---|
| author | Zhang, Stan |
| author2 | Williams, Ryan |
| author_facet | Williams, Ryan Zhang, Stan |
| author_sort | Zhang, Stan |
| collection | MIT |
| description | 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ⁿ/³). |
| first_indexed | 2024-09-23T15:59:55Z |
| format | Thesis |
| id | mit-1721.1/156830 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T15:59:55Z |
| publishDate | 2024 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1568302024-09-17T03:05:53Z Pigeonhole Equal Subset Sum in O ⃰ (2ⁿ/³) Zhang, Stan Williams, Ryan Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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ⁿ/³). MNG 2024-09-16T13:51:44Z 2024-09-16T13:51:44Z 2024-05 2024-07-11T14:37:20.533Z Thesis https://hdl.handle.net/1721.1/156830 Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) Copyright retained by author(s) https://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Zhang, Stan Pigeonhole Equal Subset Sum in O ⃰ (2ⁿ/³) |
| title | Pigeonhole Equal Subset Sum in O ⃰ (2ⁿ/³) |
| title_full | Pigeonhole Equal Subset Sum in O ⃰ (2ⁿ/³) |
| title_fullStr | Pigeonhole Equal Subset Sum in O ⃰ (2ⁿ/³) |
| title_full_unstemmed | Pigeonhole Equal Subset Sum in O ⃰ (2ⁿ/³) |
| title_short | Pigeonhole Equal Subset Sum in O ⃰ (2ⁿ/³) |
| title_sort | pigeonhole equal subset sum in o ⃰ 2ⁿ ³ |
| url | https://hdl.handle.net/1721.1/156830 |
| work_keys_str_mv | AT zhangstan pigeonholeequalsubsetsumino2n3 |