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.