期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

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

Approximation algorithms for data management in geometric networks
下载PDF
导出
摘要 针对静态数据管理问题,设计了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.
作者 幸冬梅
机构地区 南昌大学数学系 复旦大学计算机科学技术学院
出处 《计算机工程与应用》 CSCD 北大核心 2009年第21期201-205,221,共6页 Computer Engineering and Applications
基金 国家自然科学基金(No.60703091) 江西省教改基金(No.EJ0163) 南昌大学校基金(No.t1610)~~
关键词 静态数据管理 几何距离 无容量限制的设施选址问题(UFL) 近似度 static data management geometric distance Uncapacitated Facility Location（UFL） approximation ratio
分类号 TP311 [自动化与计算机技术—计算机软件与理论]
  • 相关文献

参考文献15

  • 1Dowdy W,Foster V.Comparative models of the file assignment problem[J].Computing Surveys,1982,14(2):287-313.
  • 2Krick C,Racke H,Westermann M.Approximation algorithms for data management in networks[C]//Proc of the 13th ACM Syrup on Parallel Algorithms and Architectures (SPAA 2001),Crete Island,Greece,2001:237-246.
  • 3Maggs M,Meyer F,Vocking B,et al.Exploiting locality for networks of limited bandwidth[C]//Proceedings of the 38th IEEE Symposium on Foundations of Computer Science(FOCS),1997:284-293.
  • 4Racke H.Minimizing congestion in general networks[C]//Proceeding,of the 43rd Annual Symposium on the Foundations of Computer Science,2002:43-52.
  • 5Harrelson C,Hildrum K,Rao S.A polynomial-time tree decomposition to minimize congestion[C]//Proceedings of the 15th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA),2003:34-43.
  • 6Krick C,Meyer F,Racke H,et al.Data management in networks:Experimental evaluation of a provably good strategy[C]//Theory of Computing Systems.Proceedlngs of the Eleventh Annual ACM Symposium on Parallel Algorithms and Architectures,Jun 1999:217-245.
  • 7Meyex F,Vocking B,Westermann M.Caching in networks[C]//Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms(SODA),2000:430-439.
  • 8Meyer F,Vecking B,Westermann M.Provably good and practical strategies for non-uniform data management in networks[C]//Procecdings of the 7th European Symposium on Algorithms(ESA),1999:89-100.
  • 9Awerbueh B,Bartal Y,Fiat A.Competitive distributed file allocation[C]// Proceedings of the 25th ACM Symposium on Theory of Computing (STOC),1993:164-173.
  • 10Awerbuch B,Bartal Y,Fiat A.Distributed paging for general networks[J].Journal of Algorithms,1998,28:67-104.

二级参考文献7

  • 1潘锐,朱大铭,马绍汉,肖进杰.k-Median近似计算复杂度与局部搜索近似算法分析[J].软件学报,2005,16(3):392-399. 被引量：8
  • 2D B Shmoys, E Tardos, K I Aardal. Approximation algorithms for facility location problem (extended abstract) [ C]. In: Proc of the 29th Annual ACM Syrnp on Theory of Computing. New York: ACM Press, 1997. 265 274.
  • 3S Guha, S Khuller. Greedy strikes back: Improved facility location algorithms [C]. In: Proc of the 9th Annual ACMSIAM Symp on Discrete Algorithms. Philadelphia: Society for Industrial and Applied Mathematics, 1998. 649 -657.
  • 4F A Chudak, D Shmoys. Improved approximation algorithms for the uncapacitated facility location problem [J]. SIAM Journal of Computing, 2004, 33(1): 1 -25.
  • 5M Mahdian, Y Ye, J Zhang. Improved approximation algorithms for metric facility location problems [ C]. In: Proc of the 5th Int'l Workshop on Approxlmation Algorithms for Combinatorial Optimization. Berlin; Springer-Verlag, 2002. 229 -242.
  • 6D S Hochbaum. Heuristics for the fixed cost median problem [J]. Mathematical Programming, 1982, 22(2):229-242.
  • 7M Hajiaghayi, M. Mahdian, V S Mirrokni. The facility location problem with general cost functions [J]. Networks, 2003, 42(1): 42-47.

共引文献3

计算机工程与应用
2009年 第21期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部