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

Improved approximation algorithms for relay placement

ESA 2008 · 16th Annual European Symposium on Algorithms, Karlsruhe, Germany, September 2008 · doi:10.1007/978-3-540-87744-8_30

authors’ version publisher’s version


In the relay placement problem the input is a set of sensors and a number r ≥ 1, the communication range of a relay. 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. We present a 3.11-approximation algorithm, and show that the problem admits no PTAS, assuming P ≠ NP.


Dan Halperin and Kurt Mehlhorn (Eds.): Algorithms – ESA 2008, 16th Annual European Symposium, Karlsruhe, Germany, September 15–17, 2008, Proceedings, volume 5193 of Lecture Notes in Computer Science, pages 356–367, Springer, Berlin, 2008

ISBN 978-3-540-87743-6

Journal Version

© Springer 2008

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.