Abstract
Usually the covering problem requires all elements in a system 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 k-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 presented 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 performance of our algorithms is much better than other existing k-approximation algorithm for the robust k-center problem.
Original language | English |
---|---|
Title of host publication | Proceedings of the Fifteenth IASTED International Conference on Parallel and Distributed Computing and Systems |
Pages | 541-546 |
Number of pages | 6 |
Volume | 15 |
Edition | 2 |
Publication status | Published - 1 Dec 2003 |
Event | Proceedings of the Fifteenth IASTED International Conference on Parallel and Distributed Computing and Systems - Marina del Rey, CA, United States Duration: 3 Nov 2003 → 5 Nov 2003 |
Conference
Conference | Proceedings of the Fifteenth IASTED International Conference on Parallel and Distributed Computing and Systems |
---|---|
Country/Territory | United States |
City | Marina del Rey, CA |
Period | 3/11/03 → 5/11/03 |
Keywords
- Approximation algorithms
- k-center problem
- Partial covering
ASJC Scopus subject areas
- Development
- Computer Networks and Communications
- Hardware and Architecture