Consider the following instance of the clustering problem where we have four objects p1, . . . , p4 and the distance function is given in the following table:

Suppose we want to group them into two groups (i.e., k = 2). Apply the optimal greedy algorithm to find the 2-clustering with the maximum possible spacing for these objects.

\begin{tabular}{l|c|c|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{p1} & \multicolumn{1}{c}{p2} & \multicolumn{1}{c}{p3} & \multicolumn{1}{c}{p4} \\ \cline { 2 - 5 }p1 & 0 & 8 & 2 & 3 \\ \cline { 2 - 5 }p2 & 8 & 0 & 10 & 6 \\ \cline { 2 - 5 }p3 & 2 & 10 & 0 & 2 \\ \cline { 2 - 5 }p4 & 3 & 6 & 2 & 0 \\ \cline { 2 - 5 } & & & \end{tabular}