Suppose given $2n$ points in the plane and we want to partition points into two clusters $C_1$ , $C_2$ such that each cluster contains exactly $n$ points and we want to minimize the sum of the diameters of two clusters. The diameter of a cluster is the maximum distance between any two points in that cluster.

I have a greedy algorithm for this problem:

Find diametral pair $(a,b)$ of $2n$ points, and then consider $a$ as the center of $C_1$ and $b$ as the center of $C_2$. Now, we make two lists $L_a$ and $L_b$ such that $L_a$ contains all points sorted by increasing distance from $a$ and the other by increasing distance from $b$. I keep the first $n$ points in $L_a$ that are closer to $a$ and remove others and then set $C_1=L_a$. I do the same for list $L_b$ and then set $C_2=L_b$.

My question is, the above idea is optimal or not?

I think above idea return optimal solution because I can use Exchange argument as follows:

Suppose in the optimal partitions $C'_{1}$ and $C'_2$ isn't the same as $C_1$ and $C_2$ so there exists two points $c,d$ such that $c\in C_1, d\in C_2$ and $c\in C'_2, d\in C'_1$ but according to the algorithm if we exchange $c ,d$ we get $d\in C'_2, c\in C'_1$ so we achieve a new optimal solution that it's no worse than the optimal solution. So we get contradiction.


1 Answer 1


No, the algorithm does not return the optimal sets.

Consider the case of the $4$ points $P=\{(0,0), (1,0), (0.5, 0.5), (0.5, 0.5)\}$. The diametrical points are $(0,0)$ and $(1,0)$ with distance one. So your algorithm puts them in their own clusters. The closest other-point to $(0,0)$ is $(0.5, 0.5)$ so your algorithm returns the set $\{(0,0), (0.5, 0.5)\}$ and $\{(1,0), (0.5, 0.5)\}$ with cost $\sqrt{0.5^2+0.5^2} + \sqrt{0.5^2+0.5^2}=\sqrt{2}$.

However, the optimal sets are $\{(0,0),(1,0)\}$ and $\{(0.5,0.5),(0.5,0.5)\}$ with cost $1+0=1 < \sqrt{2}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.