TY - JOUR
T1 - Improved approximation algorithms for relay placement
AU - Efrat, Alon
AU - Fekete, Sándor P.
AU - Mitchell, Joseph S.B.
AU - Polishchuk, Valentin
AU - Suomela, Jukka
N1 - Funding Information:
Parts of this research were conducted at the Dagstuhl Research Center. AE is supported by NSF CAREER grant no. 0348000. Work by SF was conducted as part of EU project FRONTS (FP7, project no. 215270.) JM is partially supported by grants from the National Science Foundation (CCF-0431030, CCF-0528209, CCF-0729019, CCF-1018388, CCF-1540890), NASA Ames, Metron Aviation, and Sandia National Labs. JS is supported in part by the Academy of Finland grant no. 116547, Helsinki Graduate School in Computer Science and Engineering (Hecse), and the Foundation of Nokia Corporation. We thank Guoliang Xue for suggesting the problem to us and for fruitful discussions, and Marja Hassinen for comments and discussions. We thank the anonymous referees for their helpful suggestions.
Publisher Copyright:
Copyright © 2015 ACM.
PY - 2015/12/1
Y1 - 2015/12/1
N2 - 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 ≠ NP.
AB - 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 ≠ NP.
KW - Approximation algorithms
KW - Polynomial-time approximation scheme (PTAS)
KW - Relays
KW - Sensor networks
KW - Steiner minimum spanning tree
KW - Wireless networks
UR - http://www.scopus.com/inward/record.url?scp=84954313620&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84954313620&partnerID=8YFLogxK
U2 - 10.1145/2814938
DO - 10.1145/2814938
M3 - Article
AN - SCOPUS:84954313620
VL - 12
JO - ACM Transactions on Algorithms
JF - ACM Transactions on Algorithms
SN - 1549-6325
IS - 2
M1 - 20
ER -