A weighted sorting problem
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 &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.