Algorithms for Disk Covering Problems with the Most Points

Bin Xiao, Qingfeng Zhuge, Yi He, Zili Shao, Edwin H M Sha

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

6 Citations (Scopus)

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 languageEnglish
Title of host publicationProceedings of the Fifteenth IASTED International Conference on Parallel and Distributed Computing and Systems
Pages541-546
Number of pages6
Volume15
Edition2
Publication statusPublished - 1 Dec 2003
EventProceedings of the Fifteenth IASTED International Conference on Parallel and Distributed Computing and Systems - Marina del Rey, CA, United States
Duration: 3 Nov 20035 Nov 2003

Conference

ConferenceProceedings of the Fifteenth IASTED International Conference on Parallel and Distributed Computing and Systems
Country/TerritoryUnited States
CityMarina del Rey, CA
Period3/11/035/11/03

Keywords

  • Approximation algorithms
  • k-center problem
  • Partial covering

ASJC Scopus subject areas

  • Development
  • Computer Networks and Communications
  • Hardware and Architecture

Cite this