An algorithm and a core set result for the weighted Euclidean one-center problem

Piyush Kumar*, E. Alper Yildirim

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

Given a set A 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 A n that minimizes the maximum weighted Euclidean distance from c A to each point in A 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 X ⊆ A, called an ε-core set of A, for which the optimal solution of the corresponding weighted Euclidean one-center problem is a close approximation to that of A. In addition, we establish that \X\ 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 A in O(mn\X\) 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.

Original languageEnglish
Pages (from-to)614-629
Number of pages16
JournalINFORMS Journal on Computing
Volume21
Issue number4
DOIs
Publication statusPublished - 1 Sep 2009

Keywords

  • Approximation algorithms
  • Core sets
  • Minimum enclosing balls
  • Weighted euclidean one-center problem

Fingerprint

Dive into the research topics of 'An algorithm and a core set result for the weighted Euclidean one-center problem'. Together they form a unique fingerprint.

Cite this