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

摘要：

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

关键词： 静态数据管理 几何距离 无容量限制 设施选址 近似策略

作者: 幸冬梅

作者单位: 南昌大学,数学系,南昌,330031;复旦大学,计算机科学技术学院,上海,200433

会议类型: 国内会议

会议名称: 2009年全国理论计算机科学学术年会

会议地点: 哈尔滨

会议语种:中文

页码: 201-205,221

在线出版日期: 2009-08-07（万方平台首次上网日期，不代表论文的发表时间）