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