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

Question

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?

Answer 1

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

Read more about integrality gap here.