Improved Approximation Algorithms for Relay Placement

Alon Efrat, Sandor P. Fekete, Joseph S. B. Mitchell, Valentin Polishchuk, Jukka Suomela

Research output: Contribution to journalArticleScientificpeer-review

6 Citations (Scopus)

Abstract

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.

Original languageEnglish
Article number20
Number of pages28
JournalACM Transactions on Algorithms
Volume12
Issue number2
DOIs
Publication statusPublished - Feb 2016
MoE publication typeA1 Journal article-refereed

Keywords

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

Fingerprint Dive into the research topics of 'Improved Approximation Algorithms for Relay Placement'. Together they form a unique fingerprint.

  • Cite this

    Efrat, A., Fekete, S. P., Mitchell, J. S. B., Polishchuk, V., & Suomela, J. (2016). Improved Approximation Algorithms for Relay Placement. ACM Transactions on Algorithms, 12(2), [20]. https://doi.org/10.1145/2814938