Improved approximation algorithms for relay placement

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

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


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.

Original languageEnglish (US)
Article number20
JournalACM Transactions on Algorithms
Issue number2
StatePublished - Dec 1 2015


  • Approximation algorithms
  • Polynomial-time approximation scheme (PTAS)
  • Relays
  • Sensor networks
  • Steiner minimum spanning tree
  • Wireless networks

ASJC Scopus subject areas

  • Mathematics (miscellaneous)


Dive into the research topics of 'Improved approximation algorithms for relay placement'. Together they form a unique fingerprint.

Cite this