Beating Meet-in-the-Middle for Subset Balancing Problems
Abstract
We consider exact algorithms for Subset Balancing, a family of related problems that generalizes Subset Sum, Partition, and Equal Subset Sum. Specifically, given as input an integer vector x→ ∈ ℤn and a constant-size coefficient set C ⊂ ℤ, we seek a nonzero solution vector c→ ∈ Cn satisfying c→ · x→ = 0.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Limits and Structures in Graph Theory
Point processes and geometric inequalities
Publication details
- Pages
- 1314–1325
- Publication date
- 9 June 2026
- Language
- EN