Upper bound algorithm how can I translate my algorithm in julia code

Hi everyone,
I am a new user of julia.
I should write an optimistic algorithm given the similarity parameters sij and the number of families r, partition the m product types into r families G1, …, Gr, each of size m/r, so as to maximize the total similarity index. let say that m=60 and r=6
my idea is:
step 1: we set an array S such that
Sij=sij si i<j
Sij= -1 si ij
we define a variable sum= 0

step 2: starting with k=1 we find w=max{Sij}
we do sum= sum + w

step 3: if si0j0 = w then we find
a= Max { Si0j } and b=max { Sij0 }

if a>b we do Si0j = -1 for each j
if a b we do Sij0 = -1 for each i

step 4:
if k<r we do
k= k+1 and then back to step 2
if k=r we continue to step 5

step 5: sum* ((((m/r)-1))*(m/r))/2) → is the upper bound

So basically I set to -1 every elements that’s in the same line or column depending on where is the biggest similarity with the object i0j0 so that later when looking for the maximum we can not find any value of interest in this line/column.
And at the end we have “sum” which will be composed of the six highest similarities that are independent which means not a same object can be twice in the same family. Then you multiply it by 45 (If we are in the instance m=60 r=6). So that means we would have in each family the biggest similarities between all the elements such that it would be 45 times this similarity in the family.

Can you please help me to write down this algorithm using julia code.

Thank you in advance

Is this a homework problem? What have you tried and what problems have you encountered?

1 Like

Please see the (draft) homework policy here: