Improved approximation algorithms for relay placement. (English)
Halperin, Dan (ed.) et al., Algorithms ‒ ESA 2008. 16th annual European symposium, Karlsruhe, Germany, September 15‒17, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-87743-1/pbk). Lecture Notes in Computer Science 5193, 356-367 (2008).
Summary: In the relay placement problem the input is a set of sensors and a number $r \geq 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 $\text {P}\ne \text {NP}$.
Start
Contact
Print
General Help
