Maximizing sum of metric function on a set (Adaptation of Hungarian Algorithm) Suppose I have a set of unique elements $A=\{a_1, a_2, ..., a_n\}$. Suppose I also have a metric function $f:A\times A \rightarrow R^+$. I want to choose $k$ elements from $A$ (i.e. $a_{i_1},a_{i_2}, ..., a_{i_k}$, $I=\{i_1,...,i_k\}$) such that it maximizes the sum:

$$S=\sum _ {i,.j\in I, i\neq j}^{}{f(a_i,a_j)}$$

Is there any known algorithm to do something like this? I know the Hungarian Algorithm can be used to solve the case of $k=n$. Can it be adapted for $k&lt;n$?
This problem is NP-hard. The decision problem of max-clique is NP-complete. Deciding whether a clique of size $k$ exists in a graph of $N$ vertices can be translated to your problem as follows. Let $A$ be the vertex set, and let $f(a_i,a_j)=1$ if the vertices are adjacent, $f(a_i,a_j)=0$ otherwise. A clique of size $k$ exists if and only if the optimal value of $S$ is $0.5 k (k-1)$.

This doesn't mean that the problem is not easy for some values of $k$ (such as $k=1$) but that an algorithm that works for any $k$ can probably not solve it in polynomial time.
This problem is NP-hard. The decision problem of max-clique is NP-complete. Deciding whether a clique of size $k$ exists in a graph of $N$ vertices can be translated to your problem as follows. Let $A$ be the vertex set, and let $f(a_i,a_j)=1$ if the vertices are adjacent, $f(a_i,a_j)=0$ otherwise. A clique of size $k$ exists if and only if the optimal value of $S$ is $0.5 k (k-1)$.

This doesn't mean that the problem is not easy for some values of $k$ (such as $k=1$) but that an algorithm that works for any $k$ can probably not solve it in polynomial time.