# Is there an algorithm to solve the following point clustering problem?

According to this post

Given $$n$$ points $$P=\{p_1,p_2,\dots,p_n\}$$ in 2D space, and a matrix $$D^{n\times n}$$ with the distances between each pair of points, we want to partition the points into two clusters so as to minimize the clusters' diameters.

This can be formulated as an integer programming problem as follows:

• Let the diameter of first cluster $$C_1$$ be $$r_1$$.
• Let the diameter of the second cluster $$C_2$$ be $$r_2$$.
• For all points $$p_i$$, let $$x_i=1$$ if $$p_i \in C_1$$, else $$x_i=-1$$.
• Determine $$min\hspace{4pt} r_1+r_2$$ such that
• $$\frac{1}{2}(x_i+x_j) D(i,j)\leq r_1 \hspace{5pt}\forall p_i,p_j$$
• $$-\frac{1}{2}(x_i+x_j) D(i,j)\leq r_2 \hspace{5pt}\forall p_i,p_j$$
• $$x_i\in\{-1,1\}.$$

My questions: is there a way to relax above ILP to find a approximation factor, and after relation how i can find the approximation factor?

• This linear programming problem has $|P|+2$ variables, so I doubt it can solve it, considering the title of the paper is "[...] Linear Programming in $\mathbb{R}^3$ [...]" Aug 27 at 21:19

Consider the natural LP relaxation of this problem, i.e., $$-1 \leq x_{i} \leq 1$$ for every $$x_i \in \{x_1,\dotsc,x_n\}$$.

Then, using the relaxation techniques, no approximation algorithm is possible since the integrality gap for this LP is $$\infty$$.

Proof: Consider any instance of this problem that has a non-zero cost. Then, in the relaxed LP, you make $$x_i = 0$$ for every $$x_i \in \{x_1,\dotsc,x_n\}$$. The optimal cost of the fractional solution will be $$0$$. Here the ratio of the optimal integral to the fractional solution is $$\infty$$; therefore the integrality gap is $$\infty$$.

• What about the running time of above LP? suppose the integrality gap is constant. Can it be solved in $o(n^3)$?
• @MohammadRostami Why are you trying LP based approach to obtain $o(n^3)$ running time. Other simple methods should be there. Aug 30 at 17:32