J4 ›› 2010, Vol. 32 ›› Issue (1): 44-46.doi: 10.3969/j.issn.1007130X.2010.
• 论文 • Previous Articles Next Articles
Received:
Revised:
Online:
Published:
Abstract:
The minimum enclosing ball problem means to construct a ball of the minimum radius enclosing a given set of balls in 〖WTBX〗S〖WTBZ〗.We propose the concept of the diameter of a set of balls and give an approximation algorithm solve the diameter. We developthe 1+ε approximation algorithm using coresets. The time complexity of this algorithm is O(nd/ε+d2/ε〖SX(〗32〖SX)〗(1/ε+d)log(1/ε)). We prove the existence of the coresets of size O(1/ε) are unrelated to n and d.
Key words: minimum enclosing ball;coreset;balls in high dimensions;approximation algorithm;computational geometry
CLC Number:
TP301.6
FAN Ke-Lei, LUAN Jun-Feng. Improved 1+ε Approximation Algorithms forthe Balls in High Dimensions via CoreSets[J]. J4, 2010, 32(1): 44-46.
0 / / Recommend
Add to citation manager EndNote|Ris|BibTeX
URL: http://joces.nudt.edu.cn/EN/10.3969/j.issn.1007130X.2010.
http://joces.nudt.edu.cn/EN/Y2010/V32/I1/44
