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$
16
  • $\begingroup$ I can't understand that why my post received negative vote? $\endgroup$
    – Jut
    Jan 1 at 19:01
  • $\begingroup$ I didn't downvote, but one possible reason is that your question seems vague, or trivial. Note that there are surely many ways to modify the greedy 2-approximation algorithm to solve your problem. But presumably that's not all you intend to ask. What kind of modifications do you have in mind? Do you, say, want a poly-time algorithm with some performance guarantee? Does it have to be greedy? Etc. $\endgroup$
    – Neal Young
    Jan 2 at 2:56
  • $\begingroup$ I want to modify above greedy algorithm $k$-center for my problem, because its running time is linear and give us 2 approximation factor. $\endgroup$
    – Jut
    Jan 2 at 14:22
  • $\begingroup$ So is it that you want to know whether there is a greedy linear-time 2-approximation algorithm for your problem, similar to the one you reference? $\endgroup$
    – Neal Young
    Jan 2 at 20:31
  • $\begingroup$ Yes, because my problem is $k$-center with additional constraint. $\endgroup$
    – Jut
    Jan 2 at 20:47
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$
15
  • $\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$
    – Jut
    Jan 4 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$
    – Jut
    Jan 4 at 19:07
  • $\begingroup$ Please give a citation for the paper? $\endgroup$
    – Neal Young
    Jan 5 at 1:55
  • $\begingroup$ This link: sciencedirect.com/science/article/pii/092577219290028Q . $\endgroup$
    – Jut
    Jan 5 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$
    – Jut
    Jan 5 at 8:09

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.