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

点击翻译按钮获取中文摘要

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.