<p>Maybe this will give ideas for a faster algorithm:</p>
<p><strong>Theorem 1.</strong> <em>There's an <span class="math-container">$O(n^2 \log n)$</span>-time 2-approximation algorithm.</em></p>
<p><em>Proof.</em> Here's the algorithm:</p>
<ol>
<li>Using binary search over the <span class="math-container">$O(n^2)$</span>-pairwise distances <span class="math-container">$\{d(u,w) : u, w\in V\}$</span>, find the minimum radius <span class="math-container">$r$</span> such that the graph <span class="math-container">$G_r=(V, E_r)$</span> is bipartite, where <span class="math-container">$E_r = E \cup\{(u,w) : d(u, w) &gt; r\}$</span>.</li>
<li>Return a bipartition of <span class="math-container">$G_r$</span>, making any vertex in each part the center of that part.</li>
</ol>
<p><em>Time.</em> The binary search requires <span class="math-container">$O(\log n)$</span> iterations, and each iteration (checking bipartiteness) can be done in <span class="math-container">$O(n^2)$</span> time, so the algorithm takes <span class="math-container">$O(n^2\log n)$</span> time.</p>
<p><em>Performance guarantee.</em> Clearly the algorithm returns a solution of value <span class="math-container">$r$</span>.  We'll show that the optimal solution has value at least <span class="math-container">$r/2$</span>.
Let <span class="math-container">$(C^*, V\setminus C^*)$</span> be an optimal solution, of value <span class="math-container">$r^*$</span>. Consider the graph <span class="math-container">$G_{2r^*}$</span> as defined in the algorithm above.  Within each cluster of the optimal solution, each point is at distance at most <span class="math-container">$r^*$</span> from its center, so all pairs of points within the cluster have distance at most <span class="math-container">$2r^*$</span>.  Also, no pairs of points within either cluster are forbidden.  It follows that no edge in <span class="math-container">$G_{2r^*}$</span> is contained in <span class="math-container">$C^*$</span> or in <span class="math-container">$V\setminus C^*$</span>, so that <span class="math-container">$(C^*, V\setminus C^*)$</span> is a bipartition of <span class="math-container">$G_{2r^*}$</span>.  So
<span class="math-container">$G_{2r^*}$</span> is bipartite.  So, by the choice of <span class="math-container">$r$</span>, <span class="math-container">$2r^* \ge r$</span>.  That is, <span class="math-container">$r\le r^*/2$</span>.  <span class="math-container">$~~~\Box$</span></p>

CC BY-SA 4.0
2022-01-04T19:04:56.523Z
I read a paper that very similar to this problem and in that, author advise a simple algorithm but i can't sense its proof of correctness of the algorithm, can i address the paper that you look at that? All the algorithm and proof is very simple and have at most 20 lines to describe the whole algorithm.
ErroR
CC BY-SA 4.0
2022-01-04T19:07:04.187Z
My problem is, I can't find out why the algorithm is correct, because in the paper i can't see any proof of correctness.
ErroR
CC BY-SA 4.0
2022-01-05T01:55:48.783Z
Please give a citation for the paper?
Neal Young
CC BY-SA 4.0
2022-01-05T08:06:29.270Z
This link: https://www.sciencedirect.com/science/article/pii/092577219290028Q .
ErroR
CC BY-SA 4.0
2022-01-05T08:09:26.730Z
My problem is, why the algorithm that described in the first section of paper, has running time $\mathcal{O}(n\log^2n)$, correct? Maybe if you describe the algorithm and its proof I will understand it. Thank you.
ErroR
CC BY-SA 4.0
2022-01-05T20:37:29.373Z
Jut, sorry, please find someone else to help you.
Neal Young
CC BY-SA 4.0
2022-01-05T20:44:18.660Z
I can describe the algorithm for you because already many times I read the paper, but i have a little problem to understand a proof.
ErroR
CC BY-SA 4.0
2022-01-05T20:55:35.023Z
Can i post it in this site to someone else help me?
ErroR
CC BY-SA 4.0
2022-01-06T03:09:25.057Z
Sure, of course.  You may wish to read https://cstheory.stackexchange.com/help/asking first, if you haven't already.
Neal Young
CC BY-SA 4.0
2022-01-08T00:53:25.470Z
Suppose given set of points $S$, can we claim that, in above problem, in any optimal solution, the diametral points $a, b$ of $S$ should be in different clusters?
ErroR
CC BY-SA 4.0
2022-01-08T00:54:07.827Z
I have a claim that proved for a case when we have no forbidden pairs.
ErroR
CC BY-SA 4.0
2022-01-08T03:06:12.810Z
No, they could be forced to be in the same cluster by the forbidden pairs.  E.g. if you have three points a, c, b with c in the middle and forbidden pairs (a,c) (c, b), then a and b have to be in the same cluster.
Neal Young
CC BY-SA 4.0
2022-01-08T11:00:51.813Z
Thank you. Is it possible to extend that lemma to work also for forbidden pairs?
ErroR
CC BY-SA 4.0
2022-01-08T17:43:46.120Z
Jut, I don't understand.  what lemma?
Neal Young
CC BY-SA 4.0
2022-01-08T22:31:00.327Z
I ask you in relevant post.
ErroR
CC BY-SA 4.0
2022-01-22T12:24:43.413Z
Hello. Consider given $n$ points in the Plane and we want partition points into $k$ clusters such that minimize some function $f$. Can we express each cluster with a leaf in some tree structure like 2D segment tree?
ErroR
CC BY-SA 4.0
2022-01-22T19:52:17.563Z
Jut, I can't help you, sorry.
Neal Young
CC BY-SA 4.0
2022-01-04T14:40:40.263Z
2022-01-04T14:40:40.263Z
Neal Young
<p>Is there a nearly linear-time 2-approximation (or <span class="math-container">$O(1)$</span>-approximation) algorithm for the following problem?</p>
<p><strong>2-Center with Forbidden Pairs</strong></p>
<p><strong>input:</strong> Bipartite graph <span class="math-container">$G=(V,E)$</span> where each vertex <span class="math-container">$v$</span> is a point <span class="math-container">$v\in\mathbb R^2$</span>.</p>
<p><strong>output:</strong> An assignment <span class="math-container">$f:V\rightarrow\{a,b\}$</span> where <span class="math-container">$\{a,b\}\subseteq V$</span> and <span class="math-container">$f(u)\ne f(w)$</span> for each <span class="math-container">$(u,w)\in E$</span>, minimizing <span class="math-container">$\max_{v\in V} d(v, f(v))$</span>, where <span class="math-container">$d(v, w)$</span> is the Euclidean distance.</p>
<p>That is, given some points in the plane with some pairs designated as &quot;forbidden&quot;, partition the points into two clusters, each with some point designated as its &quot;center&quot;, so that no forbidden pair is contained within either cluster.  Minimize the maximum distance from any point to its cluster's center.</p>
<p>The generalization to <span class="math-container">$k$</span> clusters is NP-hard for any <span class="math-container">$k\ge 3$</span>, as it subsumes <span class="math-container">$k$</span>-COLORING.</p>

CC BY-SA 4.0
2022-01-21T05:39:27.600Z
Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/133398/discussion-on-question-by-jut-2-center-problem-with-forbidden-pairs).
Bjørn Kjos-Hanssen
<ds.algorithms><approximation-algorithms>
2-Center problem with forbidden pairs
ErroR
# 2-Center problem with forbidden pairs

(Asked by: username_0 on 2021-12-31)

Is there a nearly linear-time 2-approximation (or $O(1)$-approximation) algorithm for the following problem?

**2-Center with Forbidden Pairs**

**input:** Bipartite graph $G=(V,E)$ where each vertex $v$ is a point $v\in\mathbb R^2$.

**output:** An assignment $f:V\rightarrow\{a,b\}$ where $\{a,b\}\subseteq V$ and $f(u)\ne f(w)$ for each $(u,w)\in E$, minimizing $\max\_{v\in V} d(v, f(v))$, where $d(v, w)$ is the Euclidean distance.

That is, given some points in the plane with some pairs designated as "forbidden", partition the points into two clusters, each with some point designated as its "center", so that no forbidden pair is contained within either cluster. Minimize the maximum distance from any point to its cluster's center.

The generalization to $k$ clusters is NP-hard for any $k\ge 3$, as it subsumes $k$-COLORING.

**Tags:** ds.algorithms, approximation-algorithms

> **Comments:**
> **username_1**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/133398/discussion-on-question-by-jut-2-center-problem-with-forbidden-pairs).  

---

## 1 answers

### Answer by username_2 on 2022-01-04. Score: 1 | Accepted answer

Maybe this will give ideas for a faster algorithm:

**Theorem 1.** *There's an $O(n^2 \log n)$-time 2-approximation algorithm.*

*Proof.* Here's the algorithm:

1. Using binary search over the $O(n^2)$-pairwise distances $\{d(u,w) : u, w\in V\}$, find the minimum radius $r$ such that the graph $G\_r=(V, E\_r)$ is bipartite, where $E\_r = E \cup\{(u,w) : d(u, w) > r\}$.
2. Return a bipartition of $G\_r$, making any vertex in each part the center of that part.

*Time.* The binary search requires $O(\log n)$ iterations, and each iteration (checking bipartiteness) can be done in $O(n^2)$ time, so the algorithm takes $O(n^2\log n)$ time.

*Performance guarantee.* Clearly the algorithm returns a solution of value $r$. We'll show that the optimal solution has value at least $r/2$.
Let $(C^\*, V\setminus C^\*)$ be an optimal solution, of value $r^\*$. Consider the graph $G\_{2r^\*}$ as defined in the algorithm above. Within each cluster of the optimal solution, each point is at distance at most $r^\*$ from its center, so all pairs of points within the cluster have distance at most $2r^\*$. Also, no pairs of points within either cluster are forbidden. It follows that no edge in $G\_{2r^\*}$ is contained in $C^\*$ or in $V\setminus C^\*$, so that $(C^\*, V\setminus C^\*)$ is a bipartition of $G\_{2r^\*}$. So
$G\_{2r^\*}$ is bipartite. So, by the choice of $r$, $2r^\* \ge r$. That is, $r\le r^\*/2$. $~~~\Box$

> **Comments:**
> **username_0**: I read a paper that very similar to this problem and in that, author advise a simple algorithm but i can't sense its proof of correctness of the algorithm, can i address the paper that you look at that? All the algorithm and proof is very simple and have at most 20 lines to describe the whole algorithm.  
> **username_0**: My problem is, I can't find out why the algorithm is correct, because in the paper i can't see any proof of correctness.  
> **username_2**: Please give a citation for the paper?  
> **username_0**: This link: https://www.sciencedirect.com/science/article/pii/092577219290028Q .  
> **username_0**: My problem is, why the algorithm that described in the first section of paper, has running time $\mathcal{O}(n\log^2n)$, correct? Maybe if you describe the algorithm and its proof I will understand it. Thank you.  
> **username_2**: Jut, sorry, please find someone else to help you.  
> **username_0**: I can describe the algorithm for you because already many times I read the paper, but i have a little problem to understand a proof.  
> **username_0**: Can i post it in this site to someone else help me?  
> **username_2**: Sure, of course.  You may wish to read https://cstheory.stackexchange.com/help/asking first, if you haven't already.  
> **username_0**: Suppose given set of points $S$, can we claim that, in above problem, in any optimal solution, the diametral points $a, b$ of $S$ should be in different clusters?  
> **username_0**: I have a claim that proved for a case when we have no forbidden pairs.  
> **username_2**: No, they could be forced to be in the same cluster by the forbidden pairs.  E.g. if you have three points a, c, b with c in the middle and forbidden pairs (a,c) (c, b), then a and b have to be in the same cluster.  
> **username_0**: Thank you. Is it possible to extend that lemma to work also for forbidden pairs?  
> **username_2**: Jut, I don't understand.  what lemma?  
> **username_0**: I ask you in relevant post.  
> **username_0**: Hello. Consider given $n$ points in the Plane and we want partition points into $k$ clusters such that minimize some function $f$. Can we express each cluster with a leaf in some tree structure like 2D segment tree?  
> **username_2**: Jut, I can't help you, sorry.  

---

