Given ${\cal A} := \{a^1,\ldots,a^m\} \subset \R^n$ with corresponding positive weights ${\cal W} := \{\omega_1,\ldots,\omega_m\}$, the weighted Euclidean one-center problem, which is a generalization of the minimum enclosing ball problem, involves the computation of a point $c_{\cal A} \in \R^n$ that minimizes the maximum weighted Euclidean distance from $c_{\cal A}$ to each point in ${\cal A}$. In this paper, given $\epsilon > 0$, we propose and analyze an algorithm that computes a $(1 + \epsilon)$-approximate solution to the weighted Euclidean one-center problem. Our algorithm explicitly constructs a small subset ${\cal X} \subseteq {\cal A}$, called an {\em $\epsilon$-core set} of ${\cal A}$, for which the optimal solution of the corresponding weighted Euclidean one-center problem is a close approximation to that of ${\cal A}$. In addition, we establish that $|{\cal X}|$ depends only on $\epsilon$ and the ratio of the smallest and largest weights but is independent of the number of points $m$ and the dimension $n$. This result subsumes and generalizes the previously known core set results for the minimum enclosing ball problem. Our algorithm computes a $(1+\epsilon)$-approximate solution to the weighted Euclidean one-center problem for ${\cal A}$ in \Order{mn|{\cal X}|} arithmetic operations. Our computational results indicate that the size of the $\epsilon$-core set computed by the algorithm is in general significantly smaller than the theoretical worst-case estimate, which contributes to the efficiency of the algorithm especially for large-scale instances. We shed some light on the possible reasons for this discrepancy between the theoretical estimate and the practical performance.
Citation
INFORMS Journal on Computing, 21 (4) pp. 614-629 (2009).