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?

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

Your Answer

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