- #1

- 2

- 0

I have N entities, O, each described by N values - a weight W and N-1 similarity coefficients to the other N-1 entities. I guess we can represent O

_{i}as (W

_{i}, S

_{ij, j=(1,2,...,N, i!=j})(?).

Given an integer M and M < N I need to maximize the following function:

Sum

_{i}(W

_{i}/Sum

_{j}(S

_{ij, j=(1,2,...,N), i!=j}))

where i and j in the sums are constrained to the unique combinations of the integers 1 to N of size M.

As an example let N=4, M=3 there are then 4 unique combinations of the numbers 1,2,3,4 of size 3: (1,2,3), (1,2,4), (1,3,4) and (2,3,4). The values for the function are therefore:

W

_{1}/(S

_{1,2}+S

_{1,3})+W

_{2}/(S

_{2,1}+S

_{2,3})+W

_{3}/(S

_{3,1}+S

_{3,2})

W

_{1}/(S

_{1,2}+S

_{1,4})+W

_{2}/(S

_{2,1}+S

_{2,4})+W

_{4}/(S

_{4,1}+S

_{4,2})

W

_{1}/(S

_{1,3}+S

_{1,4})+W

_{3}/(S

_{3,1}+S

_{3,4})+W

_{4}/(S

_{4,1}+S

_{4,3})

W

_{2}/(S

_{2,3}+S

_{2,4})+W

_{3}/(S

_{3,2}+S

_{3,4})+W

_{4}/(S

_{4,2}+S

_{4,3}).

For small N and M I can enumerate the combinations and calculate the maximum sum but my problem has N~50 and M~5.

Any suggestions or thoughts of an akgorithm to calulate the max? I hope I have made it clear.

Thanks in advance.