# Find a dynamic programming solution that minimize the sum of the diameters of two clusters?

I asked a question at this link, where I suggested a greedy algorithm for this problem:

Suppose given $$2n$$ points in the plane and we want 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 diameter of two clusters. The diameter of a cluster will be the maximum distance between any two points in that cluster.

An answer to that question shows the greedy approach below doesn't work:

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$$.

Now my question is, can we use a dynamic programming approach for this problem? If the answer is yes, how?

• cs.stackexchange.com/tags/dynamic-programming/info
– D.W.
Mar 6, 2022 at 6:50
• @D.W. Thank you. I am familiar with that topic but in this problem, we want to minimize the sum of diameter of two clusters. Are you have any idea about this situation?
– All
Mar 6, 2022 at 8:08
• I suggest you study the techniques found in those questions and apply the systematic procedures articulated there, then edit the question to show your progress and how far you've gotten.
– D.W.
Mar 6, 2022 at 8:57
• @D.W. It's possible for you to give me some hints?
– All
Mar 6, 2022 at 9:08