This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Kumar, P. Articles by Yildirim, E. A. Search for Related Content

An Algorithm and a Core Set Result for the Weighted Euclidean One-Center Problem

Piyush Kumar, E. Alper Yldrm

Department of Computer Science, Florida State University, Tallahassee, Florida 32306
Department of Industrial Engineering, Bilkent University, 06800 Bilkent, Ankara, Turkey
piyush{at}cs.fsu.edu
yildirim{at}bilkent.edu.tr

Given a set of m points in n-dimensional space with corresponding positive weights, the weighted Euclidean one-center problem, which is a generalization of the minimum enclosing ball problem, involves the computation of a point c ⁿ that minimizes the maximum weighted Euclidean distance from c to each point in . In this paper, given > 0, we propose and analyze an algorithm that computes a (1 + )-approximate solution to the weighted Euclidean one-center problem. Our algorithm explicitly constructs a small subset , called an -core set of , for which the optimal solution of the corresponding weighted Euclidean one-center problem is a close approximation to that of . In addition, we establish that || depends only on and on 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 + )-approximate solution to the weighted Euclidean one-center problem for in (mn||) arithmetic operations. Our computational results indicate that the size of the -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.

Key words: weighted Euclidean one-center problem; minimum enclosing balls; core sets; approximation algorithms
History: received February 2008; revised September 2008; accepted November 2008.