Suppose that I have a weighted complete graph $G$ with $N$ vertices. Is there a way to find (at least approximately) precisely $n \leq N$ vertices such that the sum of the weights of all their connecting edges is maximal?
First I thought that this may be some kind of Steiner tree, but I don't think that's the case.
Thanks!
Edit: by "maximal" I mean that I want to find vertices such that the sum of the weights of all edges that connect them is maximal, i.e. we can find no other set of vertices with a larger such sum.
As a simple example, suppose we have a (complete) graph of 4 vertices, 1, 2, 3 and 4, with weights $w_{12} = 0, w_{13} = 1 ,w_{14} = 2, w_{23} = 3, w_{24} = 4, w_{34} = 5$ and we want to pick 3 vertices with maximal sum as above, then we would pick the vertices 2, 3 and 4, since their sum would be $w_{23}+w_{24}+w_{34}=12$, which is larger than any other such sum
This is the maximum edge-weight clique (MEWC) problem. You can solve it via integer linear programming as follows. Let binary decision variable $x_i$ indicate whether node $i$ is selected. Let binary decision variable $y_{i,j}$ indicate whether edge $\{i,j\}$ is selected. The problem is to maximize $\sum_{i,j} w_{i,j} y_{i,j}$ subject to \begin{align} \sum_i x_i &= n \tag1\\ y_{i,j} &\le x_i &&\text{for all $i<j$} \tag2\\ y_{i,j} &\le x_j &&\text{for all $i<j$} \tag3 \end{align} Constraint $(1)$ selects exactly $n$ nodes. Constraints $(2)$ and $(3)$ enforce $y_{i,j} \implies (x_i \land x_j)$.