Find minimal condition number from a non-square matrix

Question

I have an optimization problem for a computational problem and I would like to know how I can solve it.

I have a matrix $\left[A\right]_{n \times m}$ with $n < m$ and I would like to get a matrix $\left[B\right]_{n \times n}$ such that $cond(B)$ is the minimal. The matrix $B$ is got by the permutation of the columns of $A$, for example:

$$ A = \left[a_{ij}\right] = \begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 6 & 7 & 8 & 9 & 10 \\ 11 & 12 & 13 & 14 & 15 \end{bmatrix}_{3 \times 5} \Longrightarrow B = \begin{bmatrix} 1 & 3 & 4 \\ 6 & 8 & 9 \\ 11 & 13 & 14 \end{bmatrix}_{3 \times 3} $$

So, the ideas that I had were:

1. Frist idea: I have $\dfrac{m!}{(m-n)!\cdot n!}$ combinations, I will make all the matrix, calculate the $cond(B)$ for each one, and get the minimal. The problem for it is the computational time, with big values of $m$ and $n$ the cost grows very fast

2. The second idea, but I don't know why this doesn't work:

   1. I get the maximum value of $A$ and I call it as $\sigma_{00}$ and it's position as $\left( l_{0}, \ c_{0} \right)$
   2. I put $0$ in all the line $l_0$ and the column $c_0$
   3. I get again the maximum value of $A$, save it like $\sigma_{11}$ and the position $(l_{1}, c_{0})$. We do it to not get a value in the same line/column that we had before.
   4. We continue until we get all the $\sigma_{ii}$, $l_{i}$ and $c_{i}$ with $i = 0, \cdots, n$
   5. Now, we get $\sigma_{ij} = A_{l_{i}, \ c_{j}}$ and we mount the matrix $\left[\sigma\right]:$

$$ \left[\sigma \right]_{n \times n} = \left[\sigma_{ij}\right] = \begin{bmatrix} 1 & \dfrac{\sigma_{01}}{\sqrt{\sigma_{00} \sigma_{11}}} & \cdots & \dfrac{\sigma_{0n}}{\sqrt{\sigma_{00} \sigma_{nn}}}\\ \dfrac{\sigma_{10}}{\sqrt{\sigma_{00} \sigma_{11}}} & 1 & \cdots & \dfrac{\sigma_{1n}}{\sqrt{\sigma_{11} \sigma_{nn}}} \\ \vdots & \vdots & \ddots & \vdots \\ \dfrac{\sigma_{n0}}{\sqrt{\sigma_{00} \sigma_{nn}}} & \dfrac{\sigma_{n1}}{\sqrt{\sigma_{11} \sigma_{nn}}} & \cdots & 1 \end{bmatrix} $$

I expected to have a matrix with all the max values in the diagonal, i.e,

$$\left\| \frac{\sigma_{ij}}{\sqrt{\sigma_{ii} \sigma_{jj}}} \right\| < 1 \ \ \ \ \forall i, j = 0, \cdots, n \ \ \ \text{and} \ \ i \ne j$$

But with my simulations, with a random matrix, I get a $\sigma$ matrix like that:

$$ A_{ex} = \begin{bmatrix} 0.5488 & 0.7152 & 0.6028 & 0.5449 & 0.4236 \\ 0.6459 & 0.4376 & 0.8918 & 0.9637 & 0.3834 \\ 0.7917 & 0.5289 & 0.5680 & 0.9256 & 0.0710 \end{bmatrix} \Rightarrow \sigma_{ex} = \begin{bmatrix} 1 & 0.7394 & 0.5271 \\ 1.0597 & 1 & 0.7029 \\ 0.6563 & 0.7293 & 1 \end{bmatrix} $$

With this exemple, $cond(B_{min}) = 7.57$, $cond(B_{max}) = 45.55$ and $cond(\sigma) = 25.59$.

Is there a better way to find the matrix $B$?