The problem:

Suppose there are $n$ points in plane, and we want to partition points into two clusters such that sum of diameter of clusters is minimized. The diameter of cluster is maximum distance between each pair of points.

My question is, how we can formulate above problem in LP manner?

My attempt:

I think so much to find a LP formulation for above problem but i have no idea.


1 Answer 1


Let $P$ be the given set of points. Declare a variable $x_p$ for every point $p \in P$ in the plane. Set $x_p = 1$ if point $p$ belongs to cluster $1$ and $x_p = -1$ if point $p$ belongs to cluster $2$. Then, the integer linear program would be as follows:

Objective function: minimize $d_1+d_2$


$\frac{(x_p + x_{p'})}{2} \cdot d(p,p') \leq d_1$ for every pair $p,p' \in P$

$-\frac{(x_p + x_{p'})}{2} \cdot d(p,p') \leq d_2$ for every pair $p,p' \in P$

$x_p \in \{1,-1 \}$ for every point $p \in P$

$d_1,d_2 \geq 0$

Here, $d(p,p')$ denotes the distance between points $p$ and $p'$.

  • $\begingroup$ @MohammadRostami $x_p + x_{p'} = 0$ $\endgroup$ Commented Aug 27, 2021 at 9:47
  • 2
    $\begingroup$ @MohammadRostami I do not think so. In general, solving an Integer linear program is NP-hard. $\endgroup$ Commented Aug 27, 2021 at 14:41

Your Answer

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

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