Given vectors $a_1, \dots, a_n\in \mathbb R^d$ where $n$ is even, I want to find partitions $I$ and $J$ of $[n]$ with $|I|=|J|=\frac n2$ to minimize $$\left\| \sum_{i\in I} a_i - \sum_{j\in J} a_j \right\|.$$ This problem can be written as a binary optimization problem. Given matrix $A = [a_1 \dots a_n]$, I want to minimize $\|Ax\|$ over $x\in\{-1,1\}^n$ and $\sum_{i=1}^n x_i=0$.
Finding exact global minimum looks NP-hard (in $d$ or $n$). Is it possible to find a nice approximate solution (like $(1+\epsilon)$-approximation for $K$-means)?
Convex relaxation does not seems to work because the convex hull of the feasible region contains a trivial global minimizer $x=0$.
Any help will greatly appreciated.
What if you relax the constraint that $x \in\{-1, 1\}^n$ into $\|x\|=1$? In other words, $$\arg\min \|Ax\| \text{ subject to } \|x\|=1 \text { and } \langle x, \underline{1}\rangle = 0$$ Once you've found a solution $x^\star$ to this problem, you just take the signum of its components.
I don't know how good an approximation this would provide