全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

网络监测节点序列部署问题的占线竞争算法设计

DOI: 10.13195/j.kzyjc.2013.0083, PP. 1513-1516

Keywords: 网络监测系统,顶点覆盖问题,占线,竞争算法

Full-Text   Cite this paper   Add to My Lib

Abstract:

万维网的高速发展需要在网络内部构建部署相应的网络监测系统,但由于耗资巨大,在设计网络监测系统时,网络节点部署初期往往不能一次性监测完所有的边,只能选择有限的网络节点以监测少部分的边,再逐渐增加部署新的网络监测节点.在占线理论与竞争策略的基础上,研究网络监测系统网络节点序列占线优化部署问题,给出一个竞争算法,证明了该算法具有常数竞争比,该竞争比结果优于已有的结果.

References

[1]  Hochbaum D. Approximation algorithms for set covering and vertex cover problems[J]. SIAM J of Computing, 1982, 11(3): 555-556.
[2]  Gandhi R, Khuller S, Srinivasan. Approximation algorithms for partial covering problems[J]. J of Algorithms, 2004, 53(1): 55-84.
[3]  Borodin A, El-Yaniv R. Online computation and competitive analysis[M]. Cambridge: Cambridge University Press, 1998.
[4]  代文强. 占线顶点覆盖问题的结构性下界[J]. 系统工程理论与实践, 2012, 32(1): 134-138.
[5]  (Dai W Q. Structural lower bound analysis for online vertex covering problem[J]. Systems Engineering-Theory & Practice, 2012, 32(1): 134-138.)
[6]  代文强. 具有建设成本的占线中心选址问题及其竞争算法设计[J]. 系统工程理论与实践, 2011, 31(12): 2342-2347.
[7]  (Dai W Q. Online median problem with constructive cost and its competitive algorithm analysis[J]. Systems Engineering-Theory & Practice, 2011, 31(12): 2342- 2347.)
[8]  Lin G, Nagarajan C, Rajaraman R, et al. A general approach for incremental approximation and hierarchical clustering[J]. SIAM J of Computing, 2010, 39(8): 3633-3669.
[9]  Korte B, Vygen J. Combinatorial optimization: Theory and Algorithms[M]. Berlin Heidelberg: Springer-Verlag, 2012.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133