Algorithms for Disk Covering Problems with the Most Points

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

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 proceeding › Conference article published in proceeding or book › Academic research › peer-review

7 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 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

Cite this

@inproceedings{4dde02c776a94454bc1d775aa3860563,

title = "Algorithms for Disk Covering Problems with the Most Points",

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.",

keywords = "Approximation algorithms, k-center problem, Partial covering",

author = "Bin Xiao and Qingfeng Zhuge and Yi He and Zili Shao and Sha, {Edwin H M}",

year = "2003",

month = dec,

day = "1",

language = "English",

isbn = "088986392X",

volume = "15",

pages = "541--546",

booktitle = "Proceedings of the Fifteenth IASTED International Conference on Parallel and Distributed Computing and Systems",

edition = "2",

note = "Proceedings of the Fifteenth IASTED International Conference on Parallel and Distributed Computing and Systems ; Conference date: 03-11-2003 Through 05-11-2003",

}

Xiao, B, Zhuge, Q, He, Y, Shao, Z & Sha, EHM 2003, Algorithms for Disk Covering Problems with the Most Points. in Proceedings of the Fifteenth IASTED International Conference on Parallel and Distributed Computing and Systems. 2 edn, vol. 15, pp. 541-546, Proceedings of the Fifteenth IASTED International Conference on Parallel and Distributed Computing and Systems, Marina del Rey, CA, United States, 3/11/03.

Algorithms for Disk Covering Problems with the Most Points. / Xiao, Bin; Zhuge, Qingfeng; He, Yi et al.
Proceedings of the Fifteenth IASTED International Conference on Parallel and Distributed Computing and Systems. Vol. 15 2. ed. 2003. p. 541-546.

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

T1 - Algorithms for Disk Covering Problems with the Most Points

AU - Xiao, Bin

AU - Zhuge, Qingfeng

AU - He, Yi

AU - Shao, Zili

AU - Sha, Edwin H M

PY - 2003/12/1

Y1 - 2003/12/1

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - k-center problem

KW - Partial covering

UR - http://www.scopus.com/inward/record.url?scp=1542642677&partnerID=8YFLogxK

M3 - Conference article published in proceeding or book

SN - 088986392X

VL - 15

SP - 541

EP - 546

BT - Proceedings of the Fifteenth IASTED International Conference on Parallel and Distributed Computing and Systems

T2 - Proceedings of the Fifteenth IASTED International Conference on Parallel and Distributed Computing and Systems

Y2 - 3 November 2003 through 5 November 2003

ER -

Algorithms for Disk Covering Problems with the Most Points

Abstract

Conference

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this