1
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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$ [...]" $\endgroup$
    – nir shahar
    Aug 27 at 21:19
1
+50
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ What about the running time of above LP? suppose the integrality gap is constant. Can it be solved in $o(n^3)$? $\endgroup$
    – Jut
    Aug 30 at 17:28
  • $\begingroup$ @MohammadRostami Yeah...I am not sure if the above ILP can be solved efficiently. $\endgroup$ Aug 30 at 17:30
  • $\begingroup$ @MohammadRostami To discuss the integrality gap, you will first need to define some relaxed LP. Many LP relaxations are possible if extra constraints are introduced. $\endgroup$ Aug 30 at 17:30
  • $\begingroup$ @MohammadRostami Why are you trying LP based approach to obtain $o(n^3)$ running time. Other simple methods should be there. $\endgroup$ Aug 30 at 17:32
  • $\begingroup$ @MohammadRostami I am thinking... :) $\endgroup$ Aug 30 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.