A study on formulation and efficient algorithms for an optimization problem in the Internet monitoring

互联网监控优化问题的表述及高效算法研究

• 批准号: 20700010
• 负责人: ZHAO Liang
• 金额: $ 1.58万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2010
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20700010/
• 关键词: 組み合わせ最適化; 頂点被覆; 支配集合問題; ビーコン配置問題; アルゴリズム; インターネット観測; グラフのカバー問題; 組合せ最適化; L-ビーコン; network monitoring; active beacon; set cover; algorithm; source routing

This study proposed "L-beacon" (where L is a nonnegative integer to decide the monitorable area of a beacon) for monitoring links in the Internet and formulated the link monitoring problem by an optimization problem for finding a minimum set of L-beacons. A very efficient algorithm, the Sieve Method, is given for solving this problem, as well as the DualSieve Method for the dual problem. The efficiency and applications of both algorithms are shown by experiments with large-scale instances. From the experiment results, it is shown that L=4, 5 are reasonable for the Internet.

本研究提出了“L-信标”（其中L是一个非负整数，以决定一个信标的监测区域）在互联网上的监测链路，并制定了一个优化问题，找到一个最小的L-信标的链路监测问题。给出了求解该问题的一种有效算法--筛法，以及求解对偶问题的双筛法。通过大规模实例的实验，验证了这两种算法的有效性和实用性。实验结果表明，L=4，5对于Internet是合理的.

项目成果

Efficient Approximate Algorithms for the Beacon Placement and its Dual Problem (Abstract)

信标放置及其对偶问题的高效近似算法（摘要）

• 发表时间: 2009
• 作者: Jiexun Wang;Jaeseong Gim;Masahiro Sasaki;Liang Zhao;Hiroshi Nagamochi
• 通讯作者: Hiroshi Nagamochi

A practical speed-up technique for A* algorithms (Abstract)

A*算法的实用加速技术（摘要）

• 发表时间: 2011
• 作者: Liang Zhao;Pipaporn Enumthurapojn;Hiroshi Nagamochi
• 通讯作者: Hiroshi Nagamochi

An A^* algorithm framework for the point-to-point time-dependent shortest path problem

点对点时间相关最短路径问题的A^*算法框架

• 发表时间: 2010
• 作者: T.Ohshima;P.Eumthurapojn;L.Zhao;H.Nagamochi
• 通讯作者: H.Nagamochi

An A* algorithm framework for the point-to-point time-dependent shortest path problem, China-Japan Joint Conference on Computational Geometry

点对点时间相关最短路径问题的A*算法框架，中日计算几何联席会议

• 发表时间: 2010
• 作者: Tatsuya Ohshima;Pipaporn Eumthurapojn;Liang Zhao;Hiroshi Nagamochi
• 通讯作者: Hiroshi Nagamochi

Security-aware beacon based network monitoring

基于安全感知信标的网络监控

• 发表时间: 2008
• 作者: Masahiro Sasaki;Liang Zhao;Hiroshi Nagamochi
• 通讯作者: Hiroshi Nagamochi