计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (21): 201-205.
• 理论科学研究 • 上一篇 下一篇
幸冬梅
收稿日期:
修回日期:
出版日期:
发布日期:
通讯作者:
XING Dong-mei
Received:
Revised:
Online:
Published:
Contact:
摘要： 针对静态数据管理问题，设计了link cost在不满足三角不等式的情况下几何网络中此问题的近似算法。通过引入两个受限的数据安置作对比，经过类似于均态分析的算法分析，在给定相关的参数的情况下，所给的近似算法具有常数的近似度。不过，网络中link cost的最大值与最小值之比是已知的。
关键词: 静态数据管理, 几何距离, 无容量限制的设施选址问题（UFL）, 近似度
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
幸冬梅. 几何网络中静态数据管理问题的近似策略[J]. 计算机工程与应用, 2009, 45(21): 201-205.
XING Dong-mei. [J]. Computer Engineering and Applications, 2009, 45(21): 201-205.
0 / 推荐
导出引用管理器 EndNote|Ris|BibTeX
链接本文: http://cea.ceaj.org/CN/
http://cea.ceaj.org/CN/Y2009/V45/I21/201
