<p>Let $A = [a_{ij}]$ be a symmetric matrix with nonnegative values and $k &lt;&lt; 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} &gt; \sum_{j=k+1}^n a_{ij}$$</p>

<p>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.</p>

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

CC BY-SA 3.0
2016-11-25T07:35:17.083Z
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
CC BY-SA 3.0
2016-11-25T18:36:14.357Z
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
<np-hardness><approximation-algorithms><linear-algebra>
Given a matrix $A$ maximize the number of positive elements in $Ax$ under specific constraints for $x$
Tanai
# Given a matrix $A$ maximize the number of positive elements in $Ax$ under specific constraints for $x$

(Asked by: username_0 on 2016-11-24)

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?

**Tags:** np-hardness, approximation-algorithms, linear-algebra

> **Comments:**
> **username_1**: 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.)  
> **username_2**: You say $k$ is *constant*.. So just try all $m \choose k$ subsets of the $m$ columns.  That's poly time for fixed $k$.  

---

## 0 answers

