Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (21): 201-205.

• 理论科学研究 • Previous Articles     Next Articles

XING Dong-mei   

  1. 1.Department of Mathematics,Nanchang University,Nanchang 330031,China
    2.School of Computer Science and Technology,Fudan University,Shanghai 200433,China
  • Received:2009-05-05 Revised:2009-07-03 Online:2009-07-21 Published:2009-07-21
  • Contact: XING Dong-mei

几何网络中静态数据管理问题的近似策略

幸冬梅   

  1. 1.南昌大学 数学系,南昌 330031
    2.复旦大学 计算机科学技术学院,上海 200433
  • 通讯作者: 幸冬梅

Abstract: An approximate strategy is designed for the static data management in geometric networks.If all parameters are given,a constant approximation ratio is achieved.Here,the link cost doesn’t satisfy triangle inequality,but the ratio between the maximum link cost and minimum link cost is known.

Key words: static data management, geometric distance, Uncapacitated Facility Location(UFL), approximation ratio

摘要: 针对静态数据管理问题,设计了link cost在不满足三角不等式的情况下几何网络中此问题的近似算法。通过引入两个受限的数据安置作对比,经过类似于均态分析的算法分析,在给定相关的参数的情况下,所给的近似算法具有常数的近似度。不过,网络中link cost的最大值与最小值之比是已知的。

关键词: 静态数据管理, 几何距离, 无容量限制的设施选址问题(UFL), 近似度