  


An Algorithm and a Core Set Result for the Weighted Euclidean OneCenter Problem
E. Alper Yildirim (yildirimbilkent.edu.tr) Abstract: 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 onecenter 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 onecenter 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 onecenter 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 onecenter 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 worstcase estimate, which contributes to the efficiency of the algorithm especially for largescale instances. We shed some light on the possible reasons for this discrepancy between the theoretical estimate and the practical performance. Keywords: Weighted Euclidean OneCenter Problem, Minimum Enclosing Balls, Core Sets, Approximation Algorithms Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: INFORMS Journal on Computing, 21 (4) pp. 614629 (2009). Download: Entry Submitted: 02/06/2008 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  