Problem $2$: Clustering Problem

$$ Input: a set of n objects C $=\{$c$1,$ c$2,...,$ cn$\}.$ Distances $($or differences$)$ between any two

objects are D $=\{$d$($ci

$,$ cj $)\}$i$,$j in $[$n$]$

$.$ An integer k $>1.$

$$ Output: Group n objects into exactly k groups that maximizes the grouping distance. The

grouping distance is defined as the minimum distance among the pairwise distances between

any two objects from different groups.

Instance: given $5$ objects C $=\{$a$,$ b$,$ c$,$ d$,$ e$\},$ distances D and k $=3.$

D $=$

a b c d e

a $09235$

b $90652$

c $26037$

d $35305$

e $52750$

Answer example, our solution is to form $3$ groups: $\{$a$\},\{$b$,$ c$\},\{$d$,$ e$\},$ and the grouping distance is

min$\{$d$($a$,$ b$),$ d$($a$,$ c$),$ d$($a$,$ d$),$ d$($a$,$ e$),$ d$($b$,$ d$),$ d$($b$,$ e$),$ d$($c$,$ d$),$ d$($c$,$ e$)\}=$ min$\{9,2,3,5,5,2,3,7\}=2.$