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

Improved approximation algorithms for relay placement

ACM Transactions on Algorithms · volume 12, issue 2, article 20, 28 pages, 2016 · doi:10.1145/2814938

authors’ version publisher’s version arXiv.org

Abstract

In the relay placement problem the input is a set of sensors and a number $r \ge 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 PTAS for the two-tier version. We also show that the one-tier version admits no PTAS, assuming P ≠ NP.

Conference Version

This is the authors’ version of the work. It is posted here for your personal use. Not for redistribution. The definitive version was be published in ACM Transactions on Algorithms.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.