Improved Approximation Algorithms for Relay Placement

Research output: Contribution to journalArticleScientificpeer-review


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

Research units

  • University of Arizona
  • Technical University of Braunschweig
  • SUNY Stony Brook, State University of New York (SUNY)
  • Linköping University


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
Issue number2
Publication statusPublished - Feb 2016
MoE publication typeA1 Journal article-refereed

    Research areas

  • 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

ID: 2039207