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

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