I have an n*n symmetric matrix, with non-negative values.
I want to remove k rows, those with the minimum row-wise sums.
Since the matrix is symmetric, after every row removal, the corresponding column will be removed too.
So, the row-wise sums will be recalculated after every removal.
Can anyone recommend a relevant optimization algorithm?
I thought to solve it as a maximum clique problem, with the weight of each node being the "row-wise sum", but I think that this does not solve the problem.
You can solve the problem via integer linear programming as follows. Let $c_{i,j}$ be the value of the $(i,j)$ entry in the matrix. Let binary variable $x_i$ indicate whether row $i$ and column $i$ are removed. Let binary variable $y_{i,j}$ indicate whether entry $(i,j)$ is removed. The problem is to maximize $\sum_{i,j} c_{i,j}(1-y_{i,j})$ subject to: \begin{align} \sum_i x_i &=k\\ x_i&\le y_{i,j}\\ x_i&\le y_{j,i} \end{align} The first constraint forces exactly $k$ rows (and the same columns) to be removed. If $x_i=1$, the second constraint forces all row $i$ entries to be removed and the third constraint forces all column $i$ entries to be removed.
Equivalently, this is a maximum edge-weighted $(n-k)$-clique problem, with edge weights $c_{i,j}$.