Computer Engineering & Science >
Improved 1+ε Approximation Algorithms forthe Balls in High Dimensions via CoreSets
Received date: 2009-04-12
Revised date: 2009-07-10
Online published: 2010-01-18
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.
FAN Ke-Lei , LUAN Jun-Feng . Improved 1+ε Approximation Algorithms forthe Balls in High Dimensions via CoreSets[J]. Computer Engineering & Science, 2010 , 32(1) : 44 -46 . DOI: 10.3969/j.issn.1007130X.2010.
/
| 〈 |
|
〉 |