<p>Assume $A$ is a $n$-dimensional matrix of real numbers. The diagonal entries are non-negative, and all other entries are non-positive. I would like to find a subset $I \subseteq \{1, 2, \ldots n\}$ of maximum size such that the sub-matrix of $A$ defined by $I$ has positive row sums, for every row. The sub-matrix of course only includes entries $A_{ij}$ such that $i, j \in I$.</p>

<p>Now, this problem generalizes max independent set, so I am not expecting anything great. Just wondering if anything at all, algorithmically, is known about this problem. Even special cases.</p>

CC BY-SA 3.0
2011-06-07T19:21:23.593Z
can u please explain why the problem generalizes max independent set. You are asking to find the sub-matrix, so i thought it is in P.
singhsumit
CC BY-SA 3.0
2011-06-07T20:02:28.027Z
You could put 0.1 on the diagonal, some large negative number in each entry representing an edge. Then the sub-matrix would only have to contain non-edges to make the row sum positive.
shortestPath
CC BY-SA 3.0
2011-06-08T02:03:58.837Z
So your row sum only sums over the index set $I$, right?
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-06-08T08:32:27.553Z
@Hsien-Chih, right.
shortestPath
<ds.algorithms><reference-request><approximation-algorithms>
Finding an index set so that row sums are positive
shortestPath
# Finding an index set so that row sums are positive

(Asked by: username_0 on 2011-06-07)

Assume $A$ is a $n$-dimensional matrix of real numbers. The diagonal entries are non-negative, and all other entries are non-positive. I would like to find a subset $I \subseteq \{1, 2, \ldots n\}$ of maximum size such that the sub-matrix of $A$ defined by $I$ has positive row sums, for every row. The sub-matrix of course only includes entries $A\_{ij}$ such that $i, j \in I$.

Now, this problem generalizes max independent set, so I am not expecting anything great. Just wondering if anything at all, algorithmically, is known about this problem. Even special cases.

**Tags:** ds.algorithms, reference-request, approximation-algorithms

> **Comments:**
> **username_1**: can u please explain why the problem generalizes max independent set. You are asking to find the sub-matrix, so i thought it is in P.  
> **username_0**: You could put 0.1 on the diagonal, some large negative number in each entry representing an edge. Then the sub-matrix would only have to contain non-edges to make the row sum positive.  
> **username_2**: So your row sum only sums over the index set $I$, right?  
> **username_0**: @Hsien-Chih, right.  

---

## 0 answers

