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

Approximation algorithms for data management in geometric networks

作　　者：幸冬梅[1,2] 

机构地区：[1]南昌大学数学系,南昌330031 [2]复旦大学计算机科学技术学院,上海200433

出　　处：《计算机工程与应用》2009年第21期201-205,221,共6页Computer Engineering and Applications

基　　金：国家自然科学基金(No.60703091);江西省教改基金(No.EJ0163);南昌大学校基金(No.t1610)~~

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

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]