Approximation algorithms design for disk partial covering problem

Bin Xiao, Jiannong Cao, Qingfeng Zhuge, Yi He, Edwin H M Sha

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

13 Citations (Scopus)

Abstract

Mobile servers are established to provide services for mobile nodes in an anticipated area. If the distribution of mobile nodes can be foreseen, the location of mobile servers becomes critical to the QoS of wireless systems. Under resource and topology constraints, it is very difficult to figure out a solution, or unable to cover all given mobile nodes within limited number of mobile servers. In this paper, we study the issue of the partial covering problem such that part of mobile nodes to be covered. Several approximation algorithms are proposed to cover the maximum number of elements. For real time systems, such as the battle-field communication system, the proposed algorithms with polynomial-time complexity can be efficiently applied. The algorithm complexity analysis illustrates the improvement made by our algorithms. The experimental results show that the performance of our algorithms is much better than other existing 3-approximation algorithm for the robust k-center problem.
Original languageEnglish
Title of host publicationProceedings of the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN
Pages104-109
Number of pages6
Publication statusPublished - 16 Aug 2004
EventProceedings on the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN - Hong Kong, Hong Kong
Duration: 10 May 200412 May 2004

Conference

ConferenceProceedings on the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN
CountryHong Kong
CityHong Kong
Period10/05/0412/05/04

ASJC Scopus subject areas

  • Computer Science(all)

Cite this