0
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.