2026-07-20T05:11:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24554 2025-12-16T14:00:45Z ddc:004 open_access

New Algorithms for Pigeonhole Equal Subset Sum Jin, Ce Williams, Ryan Zhang, Stan pigeonhole principle subset sums We study the Pigeonhole Equal Subset Sum problem, which is a total-search variant of the Subset Sum problem introduced by Papadimitriou (1994): we are given a set of n positive integers {w₁,…,w_n} with the additional restriction that ∑_{i=1}^n w_i < 2ⁿ - 1, and want to find two different subsets A,B ⊆ [n] such that ∑_{i∈A} w_i = ∑_{i∈B} w_i. Very recently, Jin and Wu (ICALP 2024) gave a randomized algorithm solving Pigeonhole Equal Subset Sum in O^*(2^{0.4n}) time, beating the classical meet-in-the-middle algorithm with O^*(2^{n/2}) runtime. In this paper, we refine Jin and Wu’s techniques to improve the runtime even further to O^*(2^{n/3}). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ce Jin and Ryan Williams and Stan Zhang 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.86 urn:nbn:de:0030-drops-245541 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.86 eng https://creativecommons.org/licenses/by/4.0/legalcode