Improved Approximation Algorithms for Relay Placement

被引：4

作者：

Efrat, Alon ^{[1
]}

Fekete, Sandor P. ^{[2
,6
]}

Mitchell, Joseph S. B. ^{[3
]}

Polishchuk, Valentin ^{[4
]}

Suomela, Jukka ^{[5
]}

机构：

[1] Univ Arizona, Dept Comp Sci, 1040 E Fourth St, Tucson, AZ 85721 USA

[2] Braunschweig Univ Technol, Braunschweig, Germany

[3] SUNY Stony Brook, Dept Appl Math & Stat, Stony Brook, NY 11794 USA

[4] Linkoping Univ, ITN, SE-60174 Norrkoping, Sweden

[5] Aalto Univ, Dept Comp Sci, Helsinki Inst Informat Technol HIIT, POB 15400, FI-00076 Aalto, Finland

[6] TU Braunschweig, Dept Comp Sci, Muhlenpfordtstr 23, D-38106 Braunschweig, Germany

来源：

ACM TRANSACTIONS ON ALGORITHMS | 2016年 / 12卷 / 02期

基金：

美国国家科学基金会; 芬兰科学院;

关键词：

Wireless networks; relays; sensor networks; approximation algorithms; Steiner minimum spanning tree; polynomial-time approximation scheme (PTAS); WIRELESS SENSOR NETWORKS; NODE PLACEMENT; MINIMUM NUMBER; STEINER TREES; CONNECTIVITY; SCHEMES; POINTS;

D O I：

10.1145/2814938

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In the relay placement problem, the input is a set of sensors and a number r >= 1, the communication range of a relay. In the one-tier version of the problem, the objective is to place a minimum number of relays so that between every pair of sensors there is a path through sensors and/or relays such that the consecutive vertices of the path are within distance r if both vertices are relays and within distance 1 otherwise. The two-tier version adds the restrictions that the path must go through relays, and not through sensors. We present a 3.11-approximation algorithm for the one-tier version and a polynomial-time approximation scheme (PTAS) for the two-tier version. We also show that the one-tier version admits no PTAS, assuming P not equal NP.

引用

页数：28

共 29 条

[1] Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems [J].

Arora, S .

JOURNAL OF THE ACM, 1998, 45 (05) :753-782

[2] APPROXIMATION ALGORITHMS FOR NP-COMPLETE PROBLEMS ON PLANAR GRAPHS [J].

BAKER, BS .

JOURNAL OF THE ACM, 1994, 41 (01) :153-180

[3]

Berman P., 1999, Automata, Languages and Programming. 26th International Colloquium, ICALP'99. Proceedings (Lecture Notes in Computer Science Vol.1644), P200

[4]

Bin Hao, 2004, 2004 Workshop on High Performance Switching and Routing (IEEE Cat. No.04TH8735), P246, DOI 10.1109/HPSR.2004.1303479

[5] Deploying Sensor Networks With Guaranteed Fault Tolerance [J].

Bredin, Jonathan L. ;

Demaine, Erik D. ;

Hajiaghayi, Mohammad Taghi ;

Rus, Daniela .

IEEE-ACM TRANSACTIONS ON NETWORKING, 2010, 18 (01) :216-228

[6]

Carmi P, 2007, LECT NOTES COMPUT SC, V4835, P644

[7] Requiring connectivity in the set covering problem [J].

Cerdeira, JO ;

Pinto, LS .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2005, 9 (01) :35-47

[8] Approximations for Steiner trees with minimum number of Steiner points [J].

Chen, DG ;

Du, DZ ;

Hu, XD ;

Lin, GH ;

Wang, LS ;

Xue, GL .

JOURNAL OF GLOBAL OPTIMIZATION, 2000, 18 (01) :17-33

[9] Approximations for Steiner trees with minimum number of Steiner points [J].

Chen, DH ;

Du, DZ ;

Hu, XD ;

Lin, GH ;

Wang, LS ;

Xue, GL .

THEORETICAL COMPUTER SCIENCE, 2001, 262 (1-2) :83-99

[10] Relay sensor placement in wireless sensor networks [J].

Cheng, Xiuzhen ;

Du, Ding-Zhu ;

Wang, Lusheng ;

Xu, Baogang .

WIRELESS NETWORKS, 2008, 14 (03) :347-355

← 1 2 3 →