3
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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$ $\endgroup$ – Suresh Venkat Apr 4 '13 at 17:48
4
$\begingroup$

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.

$\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.