B. Xiao, Q. Zhuge, Y. He, Z. Shao, and E.H.-M. Sha (USA)
Approximation algorithms, partial covering, -center prob lem.
Usually the covering problem requires all elements in a sys tem to be covered. In some situations, it is very difficult to figure out a solution, or unable to cover all given elements because of resource constraints. In this paper, we study the issue of the partial covering problem. This problem is also referred to the robust -center problem and can be applied to many fields. The partial covering problem becomes even more harder when we need to determine the subset of the group of all available elements to share resources. Several approximation algorithms are proposed to cover the most elements in this paper. For some real time systems, such as the battlefield communication system, the algorithm pre sented with polynomial-time complexity can be efficiently applied. The algorithm complexity analysis illustrates the improvement made by our algorithms, which are compared with other papers for the partial covering problem in the literature. The experimental results show that the perfor mance of our algorithms is much better than other existing 3-approximationalgorithmfor the robust -center problem.
Important Links:
Go Back
