### 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 language | English |
---|---|

Article number | 20 |

Number of pages | 28 |

Journal | ACM Transactions on Algorithms |

Volume | 12 |

Issue number | 2 |

DOIs | |

Publication status | Published - Feb 2016 |

MoE publication type | A1 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

*ACM Transactions on Algorithms*,

*12*(2), [20]. https://doi.org/10.1145/2814938