Rearrange given vectors to minimize the sum of $\ell_1$ norms of pairwise sums

Question

Let $\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_n$ be real vectors with the following property

$$\sum_{i=1}^{n}\mathbf{x}_i=0$$

I want to find a grouping strategy to achieve the minimum of

$$\|\mathbf{x}_{i_1}+\mathbf{x}_{i_2}\|_1+\|\mathbf{x}_{i_3}+\mathbf{x}_{i_4}\|_1+\cdots+\|\mathbf{x}_{i_{n-1}}+\mathbf{x}_{i_n}\|_1$$

where $\|\cdot\|_1$ is the $\ell_1$ norm.

Answer 1

Consider the algorithmic problem where you are given integer values $x_{i,k}$ and must choose a permutation $i_1,\dots,i_n$ to minimize the $\ell_1$ norm of pairwise sums.

This can be solved by finding a minimum-weight perfect matching in the graph on $[n]=\{1,\dots,n\}$ where the weight of the edge $ij$ is $|\mathbf x_i +\mathbf x_j|$. By negating the weights, finding a minimum-weight perfect matching is algorithmically equivalent to finding a maximum-weight perfect matching.

This reduction is actually an "equivalence" in a loose sense, showing that you need some sort of algorithm at least as complicated as maximum matching. For the converse direction, given a weighted graph on $[n]$, choose an arbitrary orientation of its edges, and an arbitrary enumeration of its edges, and define $x_{i,k}$ to be the weight of the $k$'th edge if $i$ is the source of edge $k$, the negation of the weight of the $k$'th edge if $i$ is the target of edge $k$, and $0$ otherwise. Then a minimum $\ell_1$-norm pairwise sum corresponds to a maximum-weight matching; each $\mathbf x_i$ contributes $|\mathbf x_i|-x_{i,k}$ to the final $\ell_1$ norm if it is paired with some $\mathbf x_j$ where $k$'th edge is $ij$. So minimising the $\ell_1$ norm means maximising the weight of the edges chosen.

Answer 2

Suppose we are given $d$-dimensional vectors $\mathrm v_1, \mathrm v_2, \dots, \mathrm v_{2n} \in \mathbb R^d$. Let $\rm V$ be the $d \times 2n$ matrix whose $k$-th column is $\mathrm v_k$. Let

$$\mathrm S := \mathrm I_n \otimes 1_2^\top = \begin{bmatrix} 1 & 1 & & & & & \\ & & 1 & 1 & & & \\ & & & \ddots & \ddots & & \\ & & & & & 1 & 1 \end{bmatrix}$$

be a $n \times 2n$ matrix. We would like to find a $2n \times 2n$ permutation matrix such that $\| \mathrm V \mathrm P \mathrm S^\top \|_1$ is minimized. Note that the we are using the following definition for the $1$-norm of an $m \times n$ matrix

$$\| \mathrm A \|_1 := \sum_{i=1}^m \sum_{j=1}^n | a_{ij} |$$

Since there are $(2n)!$ permutation matrices, we have a discrete optimization problem over the set of $2n \times 2n$ permutation matrices. Taking the convex hull of all $(2n)!$ permutation matrices, we obtain the Birkhoff polytope $B_{2n}$. Thus, we now have a continuous optimization problem in $\mathrm X \in \mathbb R^{2n \times 2n}$

$$\begin{array}{ll} \text{minimize} & \| \mathrm V \mathrm X \mathrm S^\top \|_1\\ \text{subject to} & 1_{2n}^\top \mathrm X = 1_{2n}^\top\\ & \mathrm X 1_{2n} = 1_{2n}\\ & \mathrm X \geq \mathrm O_{2n}\end{array}$$

Introducing a new matrix variable, $\mathrm Y \in \mathbb R^{d \times n}$, we obtain a linear program in $\rm X$ and $\rm Y$

$$\begin{array}{ll} \text{minimize} & \langle 1_d 1_n^\top , \mathrm Y \rangle \\ \text{subject to} & 1_{2n}^\top \mathrm X = 1_{2n}^\top\\ & \mathrm X 1_{2n} = 1_{2n}\\ & - \mathrm Y \leq \mathrm V \mathrm X \mathrm S^\top \leq \mathrm Y \\ & \mathrm X \geq \mathrm O_{2n}\end{array}$$

Let the optimal solution of this linear program be denoted by $(\mathrm X^{\star}, \mathrm Y^{\star})$. If matrix $\mathrm X^{\star}$ happens to be a permutation matrix, then we have solved the original problem.