4
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$
    – D.W. ♦
    Mar 6, 2022 at 6:50
  • $\begingroup$ @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? $\endgroup$
    – All
    Mar 6, 2022 at 8:08
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Mar 6, 2022 at 8:57
  • $\begingroup$ @D.W. It's possible for you to give me some hints? $\endgroup$
    – All
    Mar 6, 2022 at 9:08

0

Reset to default

Your Answer

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