Find binary vector furthest away from set of binary vectors?

Question

How can I find the binary vector furthest away from a set of binary vectors?

Answer 1

For $i\in\{1,\dots,n\}$ and $j\in\{1,\dots,d\}$, let $x_{i,j}\in\{0,1\}$ be the given value of vector $i$, coordinate $j$. For $j\in\{1,\dots,d\}$, let binary decision variable $y_j$ be coordinate $j$ of the desired vector. You want to maximize $$\sum_{i=1}^n \sum_{j=1}^d (x_{i,j} - y_j)^2 = \sum_{i=1}^n \sum_{j=1}^d (x^2_{i,j} - 2 x_{i,j} y_j + y_j^2) = \sum_{i=1}^n \sum_{j=1}^d (x_{i,j} - 2 x_{i,j} y_j + y_j).$$ Equivalently, maximize $$\sum_{j=1}^d y_j \sum_{i=1}^n (1-2x_{i,j}) = \sum_{j=1}^d y_j \left(n-2\sum_{i=1}^n x_{i,j}\right).$$ So take $y_j=1$ if $\sum_{i=1}^n x_{i,j} < n/2$ and $y_j=0$ otherwise.