<p>The variant of your problem where you DON'T square the distance is called the (weighted) Minimum Linear Arrangement problem. It's NP-hard and there are a number of different approximation methods for it. <a href="http://www.wisdom.weizmann.ac.il/~safro/minla/index.html">Here's one link</a> that popped up that has code that you might find useful. </p>

<p>But fortunately for you, you squared the distance, which changes things quite a bit. Let's expand the expression: 
$$
\begin{align*} 
\sum_{a,b \in A} s(a,b) (i(a) - i(b))^2 &amp;= \sum_{a,b \in A} s(a,b) (i^2(a) +i^2(b) - 2 i(a) i(b)) \\
&amp;= \sum_a i^2(a) \sum_b s(a,b) + \sum_b i^2(b) s(a,b) - 2 \sum_{a,b} s(a,b)i(a)i(b) \\
&amp;= 2 \sum_a S(a) i^2(a) - 2 \sum_{a,b} s(a,b)i(a)i(b) \\
&amp;= 2 u^\top A u 
\end{align*}
$$</p>

<p>where $u$ is the vector $i(a)$ and $A_{a,b} = -s(a,b), A(a,a) = \sum_b s(a,b)$.</p>

<p>All of this is a long-winded way of saying that you've essentially defined the Laplacian operator for the complete graph with weights given by your similarity function. At this point, minimizing the form is straightforward. You compute the decomposition of A in the form $A = V \Lambda V^T$, at which point your goal is to minimize the norm $\| u^T V \sqrt{\Lambda}\|$. But note that since $A$ is symmetric, $V$ is orthonormal, and is essentially a rotation matrix, and so what you really want to do is line up $u$ in reverse order of the eigenvalues of $A$ (the elements of $\Lambda$)</p>

CC BY-SA 3.0
2011-11-09T07:36:34.133Z
2011-11-09T07:36:34.133Z
Suresh Venkat
<p>While thinking about the best way to display confusion matrices, and I came up with the following problem:</p>

<p>You have a set of objects $A$, and a similarity function $s: A,A \rightarrow \mathbb{R}$ defined on every pair of objects.  You want to find an ordering $i: A \rightarrow [1..|A|]$ on the objects that minimizes:</p>

<p>$\sum_{a,b \in A} s(a,b) * (i(a) - i(b))^2$</p>

<p>That is, the ordering is penalized by the similarity of each pair times the square of the distance.</p>

<p>Any ideas on an algorithm to solve this?  Any of: a polynomial-time algorithm, an idea for an NP-hard reduction, or search keywords for similar problems would be greatly appreciated.  Thanks!</p>

<ds.algorithms><total-ordering>
Algorithm for ordering a list under a similarity function?
Max Libbrecht
# Algorithm for ordering a list under a similarity function?

(Asked by: username_0 on 2011-11-09)

While thinking about the best way to display confusion matrices, and I came up with the following problem:

You have a set of objects $A$, and a similarity function $s: A,A \rightarrow \mathbb{R}$ defined on every pair of objects. You want to find an ordering $i: A \rightarrow [1..|A|]$ on the objects that minimizes:

$\sum\_{a,b \in A} s(a,b) \* (i(a) - i(b))^2$

That is, the ordering is penalized by the similarity of each pair times the square of the distance.

Any ideas on an algorithm to solve this? Any of: a polynomial-time algorithm, an idea for an NP-hard reduction, or search keywords for similar problems would be greatly appreciated. Thanks!

**Tags:** ds.algorithms, total-ordering

---

## 1 answers

### Answer by username_1 on 2011-11-09. Score: 7 | Accepted answer

The variant of your problem where you DON'T square the distance is called the (weighted) Minimum Linear Arrangement problem. It's NP-hard and there are a number of different approximation methods for it. [Here's one link](http://www.wisdom.weizmann.ac.il/~safro/minla/index.html) that popped up that has code that you might find useful.

But fortunately for you, you squared the distance, which changes things quite a bit. Let's expand the expression:
$$
\begin{align\*}
\sum\_{a,b \in A} s(a,b) (i(a) - i(b))^2 &= \sum\_{a,b \in A} s(a,b) (i^2(a) +i^2(b) - 2 i(a) i(b)) \\
&= \sum\_a i^2(a) \sum\_b s(a,b) + \sum\_b i^2(b) s(a,b) - 2 \sum\_{a,b} s(a,b)i(a)i(b) \\
&= 2 \sum\_a S(a) i^2(a) - 2 \sum\_{a,b} s(a,b)i(a)i(b) \\
&= 2 u^\top A u
\end{align\*}
$$

where $u$ is the vector $i(a)$ and $A\_{a,b} = -s(a,b), A(a,a) = \sum\_b s(a,b)$.

All of this is a long-winded way of saying that you've essentially defined the Laplacian operator for the complete graph with weights given by your similarity function. At this point, minimizing the form is straightforward. You compute the decomposition of A in the form $A = V \Lambda V^T$, at which point your goal is to minimize the norm $\| u^T V \sqrt{\Lambda}\|$. But note that since $A$ is symmetric, $V$ is orthonormal, and is essentially a rotation matrix, and so what you really want to do is line up $u$ in reverse order of the eigenvalues of $A$ (the elements of $\Lambda$)


---

