<p>It is NP-hard. Here is a reduction from the minimum bisection problem. Let $G = ([n],E)$ be a graph on $n$ vertices with $m$ edges (assume that $n$ is even). Let $N=2m$. Let $y= (1,\dots, 1,-1,\dots,-1)$ consist of $n/2$ ones and $n/2$ minus ones. For every edge $(i,j)$ introduce two columns: one with ones at positions $i$ and $j$, the other with $-1$ at positions $i$ and $j$. Each permutation $P$ defines a bisection $(S,\bar S)$ and vice versa: 
$$S=\{i:1\leq P(i) \leq n/2\} \qquad \bar S=\{i:n/2+1 \leq P(i) \leq n\}.$$
($P$ is not uniquely defined by $S$; but all permutations corresponding to $S$ are equivalent).</p>

<p>If an edge $(i,j)$ is not cut by $(S,\bar S)$ then it contributes $C_1 = \sqrt{n-2}+\sqrt{n+6}$ to the objective function. If $(i,j)$ is cut then it contributes $C_2 = \sqrt{n+2}+\sqrt{n+2}$. Let $\Delta = C_2 - C_1 &gt; 0$. 
Observe that the value of the problem equals $m C_1 + \Delta\cdot |E(S,\bar S)|$. That is, the optimal solution to this problem corresponds to the minimum bisection and vice versa.</p>

CC BY-SA 3.0
2013-04-04T18:19:45.277Z
2013-04-04T18:19:45.277Z
Yury
<p>Given a data matrix $D=[d_1 ... d_N]$, one would like to sort it in terms of rows such that the weighted distance of sorted $d$s to a target vector $y$ is being minimized. </p>

<p>It can be formulated as follows</p>

<p>$\min_{P\in\Pi} \sum_i w_i ||Pd_i-y||_2 $</p>

<p>where $w_i$ is the weight, $\Pi$ is the set of permutation matrix: $\Pi = \{P|Pe=e,P^Te=e,P_{ij}\in \{0,1\}\}$</p>

<p>Is there any optimal sorting strategy? </p>

CC BY-SA 3.0
2013-04-04T17:48:57.243Z
If you used the sum of squares inside the cost function, this gets a lot easier, and reduces to finding a best mapping from a single fixed vector to $y$
Suresh Venkat
<cc.complexity-theory><ds.algorithms><optimization><sorting>
A weighted sorting problem
Rein
# A weighted sorting problem

(Asked by: username_0 on 2013-04-04)

Given a data matrix $D=[d\_1 ... d\_N]$, one would like to sort it in terms of rows such that the weighted distance of sorted $d$s to a target vector $y$ is being minimized.

It can be formulated as follows

$\min\_{P\in\Pi} \sum\_i w\_i ||Pd\_i-y||\_2 $

where $w\_i$ is the weight, $\Pi$ is the set of permutation matrix: $\Pi = \{P|Pe=e,P^Te=e,P\_{ij}\in \{0,1\}\}$

Is there any optimal sorting strategy?

**Tags:** cc.complexity-theory, ds.algorithms, optimization, sorting
> **Comments:**
> **username_1**: If you used the sum of squares inside the cost function, this gets a lot easier, and reduces to finding a best mapping from a single fixed vector to $y$  

---

## 1 answers

### Answer by username_2 on 2013-04-04. Score: 4 | Accepted answer

It is NP-hard. Here is a reduction from the minimum bisection problem. Let $G = ([n],E)$ be a graph on $n$ vertices with $m$ edges (assume that $n$ is even). Let $N=2m$. Let $y= (1,\dots, 1,-1,\dots,-1)$ consist of $n/2$ ones and $n/2$ minus ones. For every edge $(i,j)$ introduce two columns: one with ones at positions $i$ and $j$, the other with $-1$ at positions $i$ and $j$. Each permutation $P$ defines a bisection $(S,\bar S)$ and vice versa:
$$S=\{i:1\leq P(i) \leq n/2\} \qquad \bar S=\{i:n/2+1 \leq P(i) \leq n\}.$$
($P$ is not uniquely defined by $S$; but all permutations corresponding to $S$ are equivalent).

If an edge $(i,j)$ is not cut by $(S,\bar S)$ then it contributes $C\_1 = \sqrt{n-2}+\sqrt{n+6}$ to the objective function. If $(i,j)$ is cut then it contributes $C\_2 = \sqrt{n+2}+\sqrt{n+2}$. Let $\Delta = C\_2 - C\_1 > 0$.
Observe that the value of the problem equals $m C\_1 + \Delta\cdot |E(S,\bar S)|$. That is, the optimal solution to this problem corresponds to the minimum bisection and vice versa.


---

