A Faster Algorithm for Pigeonhole Equal Sums
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917624710955008 |
|---|---|
| author | Jin, Ce Wu, Hongxun |
| author_facet | Jin, Ce Wu, Hongxun |
| contents | 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ö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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_19117 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Faster Algorithm for Pigeonhole Equal Sums Jin, Ce Wu, Hongxun Data Structures and Algorithms 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ö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. |
| title | A Faster Algorithm for Pigeonhole Equal Sums |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2403.19117 |