• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊
论文

Improved 1+ε Approximation Algorithms forthe Balls in High Dimensions via CoreSets

  • FAN Ke-Lei ,
  • LUAN Jun-Feng
Expand
  • (School of Computer Science and Technology,Shandong University,Jinan 250101,China)

Received date: 2009-04-12

  Revised date: 2009-07-10

  Online published: 2010-01-18

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 coresets. The time complexity of this algorithm is O(nd/ε+d2/ε〖SX(〗32〖SX)〗(1/ε+d)log(1/ε)). We prove the existence of the coresets of size O(1/ε) are unrelated to n and d.

Cite this article

FAN Ke-Lei , LUAN Jun-Feng . Improved 1+ε Approximation Algorithms forthe Balls in High Dimensions via CoreSets[J]. Computer Engineering & Science, 2010 , 32(1) : 44 -46 . DOI: 10.3969/j.issn.1007130X.2010.

Outlines

/