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\_{\substack{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.



Finding a $k$-subset which maximizes a matrix sum
This is the 0-1 [quadratic knapsack problem](https://en.wikipedia.org/wiki/Quadratic_knapsack_problem), which is NP-hard. The binary decision variables $x\_i$ indicate whether $i\in S$, and the knapsack capacity is $k$.


You can solve it via integer linear programming as follows. For $i<j$, let binary decision variable $y\_{i,j}$ represent $x\_i x\_j$. The problem is to maximize $\sum\_i M\_{i,i} x\_i + \sum\_{i<j} (M\_{i,j}+M\_{j,i}) y\_{i,j}$ subject to
\begin{align}
y\_{i,j} &\le x\_i &\text{for $i<j$} \tag1 \\
y\_{i,j} &\le x\_j &\text{for $i<j$} \tag2 \\
y\_{i,j} &\ge x\_i + x\_j - 1 &\text{for $i<j$} \tag3 \\
\sum\_i x\_i &\le k \tag4
\end{align}
Constraint $(1)$ enforces $y\_{i,j} \implies x\_i$.
Constraint $(2)$ enforces $y\_{i,j} \implies x\_j$.
Constraint $(3)$ enforces $(x\_i \land x\_j) \implies y\_{i,j}$.
Constraint $(4)$ enforces $|S| \le k$.


If $M\_{i,j} \ge 0$, you can omit $(3)$, which will naturally be satisfied because of the objective.


