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

一类median问题的近似算法研究 被引量：1

Research on approximation algorithm for a kind of median problem
下载PDF
导出
摘要 利用Lin和Vitter的过滤思想研究了完全图的赋权median问题,并给出了一个近似算法.此算法可在最小化破坏背包约束的条件下求得问题的一个近似比为1+ε(ε>0)的解. The idea of filtering due to Lin and Vitter is used to study the weighted median problem in complete graphs, and an approximation algorithm is presented, which outputs a solution of approximation ratio 1 ＋ ε （ arbitary ε 〉 0） to this problem with minimum packing constraint violations.
作者 王继强
机构地区 山东大学数学与系统科学学院
出处 《山东大学学报（理学版）》 CAS CSCD 北大核心 2006年第4期1-3,共3页 Journal of Shandong University(Natural Science)
基金 国家自然科学基金资助项目(10271065)
关键词 MEDIAN 过滤规划 集合覆盖 近似算法 median filtered program set cover approximation algorithm
分类号 O224 [理学—运筹学与控制论]
  • 相关文献

参考文献5

  • 1J H Lin,J S Vitter.ε-Approximations with minimum packing constraint violations[A].Proceedings of the 24th Annual ACM STOC[C].Toronto:Academic Press,1992.771～781
  • 2N Karmarkar.A new polynomial-time algorithm for linear programming[J].Combinatorca,1984,4:373～395.
  • 3L G Khachiyan.A polynomial algorithm in linear programming[J].Soviet Math,1979,20:191～194.
  • 4V Chvátal.A greedy heuristic for the set covering problem[J].Mathematics of Operations Research,1979,4:233～235.
  • 5L Lavász.On the ratio of optimal integral and fractional covers[J].Discrete Mathematics,1975,13:383～390.

同被引文献11

  • 1杨丰梅,华国伟,邓猛,黎建强.选址问题研究的若干进展[J].运筹与管理,2005,14(6):1-7. 被引量：75
  • 2RANGANATHAN K, FOSTER I. Identifying dynamic replication strategies for a high performance data grid[C]// CRAIG A L. In Proc. of the 2nd International Workshop on Grid Computing. Berlin: Springer-Verlag, 2001 : 59-64.
  • 3RANGANATHAN K, FOSTER I. Design and evaluation of dynamic replication strategies for a high-performance data grid[EB/OL]. (2001-09-03)[2008- 01-10] http://www, globus, org/alliance/publications/papers/repChep01, pdf.
  • 4WILLIAM H B, DAVID G C, RUBEN C S, et al. Evaluation of an economy-based file replication strategy for a data grid[C]//MINRA K. In International Workshop on Agent Based Cluster and Grid Computing at CCGrid2003. Tokyo: IEEE Computer Society Press, 2003 : 101-106.
  • 5CARMAN M. Towards an economy-based optimisation of fie access and replication on a data grid[C]// PARASHAR M. Cluster Computing and the Grid (CCGrid'02). Berlin: Springer, 2002:76-83.
  • 6RAHMAN R M, BARKER K, ALHAJJ R. Replica placement design with static optimality and dynamic maintainability grid[C]// STEPHEN J. In Proc. of the Sixth IEEE International Symposium on Cluster Computing and the Grid (CCGRID'06). Singapore: IEEE Computer Society, 2006:41-47.
  • 7KARIV O, HAKIMI S L. An algorithmic approach to network location problems [J]. SIAM Journal Applied Mathematics, 1979(37) :539-560.
  • 8WSOLOWSKY G, TRUSCOTT W. The multi-period location allocation problem with relocation of facilities[J]. Management Science, 1975 (22): 57- 65.
  • 9CAMERON D G, MILLAR A P, NICHOLSON L, et al. Analysis of scheduling and replica optimisation strategies for data grids using optorsim[J]. Journal of Grid Computing, 2004(2) : 57-69.
  • 10DAVID G C, RUBEN C S, PAUL A M. UK Grid simulation with optorsim [J]. European Organization for Nuclear Research, 2003(1):23-30.

引证文献1

二级引证文献6

山东大学学报（理学版）
2006年 第4期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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