Improved Approximation Algorithms for Relay Placement
2016 (English)In: ACM Transactions on Algorithms, ISSN 1549-6325, E-ISSN 1549-6333, Vol. 12, no 2, 20- p.Article in journal (Refereed) PublishedText
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.
Place, publisher, year, edition, pages
ACM Press, 2016. Vol. 12, no 2, 20- p.
Wireless networks; relays; sensor networks; approximation algorithms; Steiner minimum spanning tree; polynomial-time approximation scheme (PTAS)
IdentifiersURN: urn:nbn:se:liu:diva-127756DOI: 10.1145/2814938ISI: 000373905400008OAI: oai:DiVA.org:liu-127756DiVA: diva2:927482
Funding Agencies|EU project FRONTS (FP7) ; National Science Foundation [CCF-0431030, CCF-0528209, CCF-0729019, CCF-1018388, CCF-1540890, 0348000]; NASA Ames; Metron Aviation; Sandia National Labs; Academy of Finland ; Helsinki Graduate School in Computer Science and Engineering (Hecse); Foundation of Nokia Corporation2016-05-122016-05-122016-05-12