Finding a $k$-subset which maximizes a matrix sum

Question

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.

Answer 1

This is the 0-1 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.