Sort binary matrix by swapping columns to make subrectangle of ones with maximum size
Yes, you can solve it faster than trying all possible permutations.

The biggest such rectangle must span consecutive rows.  So, for all $i,j$ with $i \le j$, check what is the biggest rectangle you can make that spans rows $i..j$.  You can do this check in $O(mn)$ time, by checking which columns have a 1 in all of those rows.  There are only $O(m^2)$ possible values of $i,j$. 

So, the running time of this simple method is $O(m^3 n)$, which is faster than trying all permutations.  (Trying all permutations would take $\Omega(m \cdot n!)$ time, which is far slower -- it is exponential time, rather than polynomial time.)  I make no claim that this simple method is optimal -- rather, I merely claim that the answer to your question is "yes".