There are n data items (d1, d2, .. , dn) and an integer m less than equal to n.
Next you are given a NxN matrix SIM such that SIM[i][j] = similarity between di and dj.

For every data item di, Choose any m-sized subset s of the n items and evaluate sum of similarities between di and dj such that dj belongs to the chosen subset s, call this value the score for di given subset s or d(i,s).

Define Si = score of data item i = max d(i,S) over all possible m sized subsets S

find x where x = max Si over all i (from 1 to n)
if there is more than 1 valid answer then minimize x.

SIM[i][j] = SIM[j][i].
1 <= m <= n <= 1000

n = 3, m = 2.
SIM :
10 6 -4
6 10 -2
-4 -2 10

all possible 2 sized subsets are {1,2}, {1,3}, {2, 3}.
score for d1 = max{(10+6), (10-4), (6-4)} = 16
score for d2 = max{(6+10), (6-2), (10-2)} = 16
score for d3 = max{(-4-2), (-4+10), (-2+10)} = 8

possible answers 1 and 2, choose the minimum.
therefore output 1.

Brute force : Overall complexity : n * binomial_coeff(n,m)

DP : dp[i][j][k] = max(dp[i][j-1][k], SIM[i][j] + dp[i][j-1][k-1]), score for the ith item, taking a k sized subset of the 1st j items.
Si = dp[i][n][m].
Overall complexity : n*n*m

Greedy1 : for every i,
put all values SIM[i][j] for all j from 1 to n in a vector. sort this vector, take sum of last m items. This is Si.
Overall complexity : n*n*log(n)

Greedy2 : Use heap instead of sorting.
Overall complexity : n*n*log(m)