<p>Let <span class="math-container">$M\in \mathbb{R}^{N\times N}$</span> be a given matrix and <span class="math-container">$k\ge 2$</span> be a given integer. Then my question is the following optimization problem:</p>
<p>Is there a polynomial-time solution to the following problem: <span class="math-container">$$S^\star = \arg\max_{S\subset [N]:\\ |S|\le k} \sum_{i,j\in S}M_{ij}.$$</span></p>
<p>This seems to be hard in general (that is, it requires exponential time-complexity), but I could not find a direct link to any known problem. I first thought that this problem is related to the maximum subset problem, but I am not sure. It will be really helpful if somebody can provide any reference to any related problem. It seems that approximate solutions can be found for this problem, but I was unable to find that too after a Google search. It will be really great if someone can give any reference.
Thanks in advance.</p>

CC BY-SA 4.0
2021-10-02T19:43:25.560Z
WLOG you can assume $M$ is symmetric (because the term $M_{ij}$ is counted iff the term $M_{ji}$ is counted).  So the problem is equivalent to the following: given a graph with (possibly negative) edge weights, find a subset of at most $k$ vertices that maximizes the total weight of the edges in the induced subgraph.  In the case that $M$ is a symmetric 0/1 matrix, this is equivalent to the [densest $k$-subgraph problem](https://en.wikipedia.org/wiki/Dense_subgraph#Densest_k_subgraph), which is NP-hard as it generalizes CLIQUE.  (And see the wikipedia link for more details.)
Neal Young
CC BY-SA 4.0
2021-10-02T20:32:38.613Z
asked simultaneously and answered on mathoverflow https://mathoverflow.net/questions/405318/finding-a-k-subset-which-maximizes-a-matrix-sum
kodlu
CC BY-SA 4.0
2021-10-03T12:01:09.887Z
p.s. The link to the densest subgraph problem discusses approximation algorithms including hardness of approximation.
Neal Young
CC BY-SA 4.0
2021-10-04T15:01:57.673Z
Thanks for the very informative comments!
Samrat Mukhopadhyay
<optimization><time-complexity>
Finding the best $k-$subset which maximizes a matrix sum
Samrat Mukhopadhyay
# Finding the best $k-$subset which maximizes a matrix sum

(Asked by: username_0 on 2021-10-02)

Let $M\in \mathbb{R}^{N\times N}$ be a given matrix and $k\ge 2$ be a given integer. Then my question is the following optimization problem:

Is there a polynomial-time solution to the following problem: $$S^\star = \arg\max\_{S\subset [N]:\\ |S|\le k} \sum\_{i,j\in S}M\_{ij}.$$

This seems to be hard in general (that is, it requires exponential time-complexity), but I could not find a direct link to any known problem. I first thought that this problem is related to the maximum subset problem, but I am not sure. It will be really helpful if somebody can provide any reference to any related problem. It seems that approximate solutions can be found for this problem, but I was unable to find that too after a Google search. It will be really great if someone can give any reference.
Thanks in advance.

**Tags:** optimization, time-complexity
> **Comments:**
> **username_1**: WLOG you can assume $M$ is symmetric (because the term $M_{ij}$ is counted iff the term $M_{ji}$ is counted).  So the problem is equivalent to the following: given a graph with (possibly negative) edge weights, find a subset of at most $k$ vertices that maximizes the total weight of the edges in the induced subgraph.  In the case that $M$ is a symmetric 0/1 matrix, this is equivalent to the [densest $k$-subgraph problem](https://en.wikipedia.org/wiki/Dense_subgraph#Densest_k_subgraph), which is NP-hard as it generalizes CLIQUE.  (And see the wikipedia link for more details.)  
> **username_2**: asked simultaneously and answered on mathoverflow https://mathoverflow.net/questions/405318/finding-a-k-subset-which-maximizes-a-matrix-sum  
> **username_1**: p.s. The link to the densest subgraph problem discusses approximation algorithms including hardness of approximation.  
> **username_0**: Thanks for the very informative comments!  

---

## 0 answers

