1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ Jan 21, 2022 at 5:39

1 Answer 1

1
$\begingroup$

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$

$\endgroup$
17
  • $\begingroup$ 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. $\endgroup$
    – MR_
    Jan 4, 2022 at 19:04
  • $\begingroup$ 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. $\endgroup$
    – MR_
    Jan 4, 2022 at 19:07
  • $\begingroup$ Please give a citation for the paper? $\endgroup$
    – Neal Young
    Jan 5, 2022 at 1:55
  • $\begingroup$ This link: sciencedirect.com/science/article/pii/092577219290028Q . $\endgroup$
    – MR_
    Jan 5, 2022 at 8:06
  • $\begingroup$ 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. $\endgroup$
    – MR_
    Jan 5, 2022 at 8:09

Your Answer

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

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