Subset Balancing and Generalized Subset Sum via Lattices
This work addresses computational complexity challenges in combinatorial optimization for researchers in algorithms and lattice theory, offering incremental improvements over prior methods.
The paper tackles the Subset Balancing problem by reducing it to lattice problems, achieving deterministic and randomized algorithms with running times of approximately O(2^{4.632n}) and O(2^{2.443n}), respectively, and shows polynomial-time solvability for large d.
We study the \emph{Subset Balancing} problem: given $\mathbf{x} \in \mathbb{Z}^n$ and a coefficient set $C \subseteq \mathbb{Z}$, find a nonzero vector $\mathbf{c} \in C^n$ such that $\mathbf{c}\cdot\mathbf{x} = 0$. The standard meet-in-the-middle algorithm runs in time $\tilde{O}(|C|^{n/2})=\tilde{O}(2^{n\log |C|/2})$, and recent improvements (SODA~2022, Chen, Jin, Randolph, and Servedio; STOC~2026, Randolph and WÄgrzycki) beyond this barrier apply mainly when $d$ is constant. We give a reduction from Subset Balancing with $C = \{-d, \dots, d\}$ to a single instance of $\mathrm{SVP}_{\infty}$ in dimension $n+1$, which yields a deterministic algorithm with running time $\tilde{O}((6\sqrt{2Ïe})^n) \approx \tilde{O}(2^{4.632n})$, and a randomized algorithm with running time $\tilde{O}(2^{2.443n})$ (here $\tilde{O}$ suppresses $\operatorname{poly}(n)$ factors). We also show that for sufficiently large $d$, Subset Balancing is solvable in polynomial time. More generally, we extend the box constraint $[-d,d]^n$ to an arbitrary centrally symmetric convex body $K \subseteq \mathbb{R}^n$ with a deterministic $\tilde{O}(2^{c_K n})$-time algorithm, where $c_K$ depends only on the shape of $K$. We further study the \emph{Generalized Subset Sum} problem of finding $\mathbf{c} \in C^n$ such that $\mathbf{c} \cdot \mathbf{x} = Ï$. For $C = \{-d, \dots, d\}$, we reduce the worst-case problem to a single instance of $\mathrm{CVP}_{\infty}$. Although no general single exponential time algorithm is known for exact $\mathrm{CVP}_{\infty}$, we show that in the average-case setting, for both $C = \{-d, \dots, d\}$ and $C = \{-d, \dots, d\} \setminus \{0\}$, the embedded instance satisfies a bounded-distance promise with high probability. This yields a deterministic algorithm running in time $\tilde{O}((18\sqrt{2Ïe})^n) \approx \tilde{O}(2^{6.217n})$.