Given a matrix $A$ maximize the number of positive elements in $Ax$ under specific constraints for $x$

Let $A = [a_{ij}]$ be a symmetric matrix with nonnegative values and $k << n/2$ a given constant. We want to rearrange the columns of the matrix such that the number of rows with the following property is maximized: $$\sum_{j=1}^k a_{ij} > \sum_{j=k+1}^n a_{ij}$$

I have tried a greedy approach as well as to choose the $k$ columns with the largest sum. I think there is also a connection with the 2-partition of a set into sets such that the difference of their sums is maximized, but I have not any proofs.

Any ideas? Is there an efficient optimal or approximate algorithm for the problem? Can we prove if it is NP-hard?

• For nonsymmetric 0/1-matrices, this is NP-hard. (Sorry, I forgot the symmetric part when I went into the shower, so I solved a different problem.) – Radu GRIGore Nov 25 '16 at 7:35
• You say $k$ is constant.. So just try all $m \choose k$ subsets of the $m$ columns. That's poly time for fixed $k$. – Neal Young Nov 25 '16 at 18:36