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?

  • 2
    $\begingroup$ 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.) $\endgroup$ – Radu GRIGore Nov 25 '16 at 7:35
  • 3
    $\begingroup$ You say $k$ is constant.. So just try all $m \choose k$ subsets of the $m$ columns. That's poly time for fixed $k$. $\endgroup$ – Neal Young Nov 25 '16 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.