A Faster Algorithm for Pigeonhole Equal Sums
<|reference_start|>A Faster Algorithm for Pigeonhole Equal Sums: An important area of research in exact algorithms is to solve Subset-Sum-type problems faster than meet-in-middle. In this paper we study Pigeonhole Equal Sums, a total search problem proposed by Papadimitriou (1994): given $n$ positive integers $w_1,\dots,w_n$ of total sum $\sum_{i=1}^n w_i < 2^n-1$, the task is to find two distinct subsets $A, B \subseteq [n]$ such that $\sum_{i\in A}w_i=\sum_{i\in B}w_i$.   Similar to the status of the Subset Sum problem, the best known algorithm for Pigeonhole Equal Sums runs in $O^*(2^{n/2})$ time, via either meet-in-middle or dynamic programming (Allcock, Hamoudi, Joux, Klingelh\"{o}fer, and Santha, 2022).   Our main result is an improved algorithm for Pigeonhole Equal Sums in $O^*(2^{0.4n})$ time. We also give a polynomial-space algorithm in $O^*(2^{0.75n})$ time. Unlike many previous works in this area, our approach does not use the representation method, but rather exploits a simple structural characterization of input instances with few solutions.<|reference_end|>
@article{jin2024a,
    title={A Faster Algorithm for Pigeonhole Equal Sums},
    author={Ce Jin and Hongxun Wu},
    journal={arXiv preprint arXiv:2403.19117},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.19117},
    primaryClass={cs.DS}
}