# Given $n$ vectors, find partitions with closest centroids

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.

• Looks like a multidimensional generalization of the partition problem (unless the restriction $|I|=|J|$ makes a big difference, not sure). – Rahul Jan 25 at 4:13
• @Rahul Thanks for pointing this out. It is interesting enough to consider the problem without the restriction. Can the algorithm generalize to multidimensional case? – Mayu Jan 25 at 5:56

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.