Improved approximation algorithms for relay placement

Conference paper

Authors:	Alon Efrat, Sándor P. Fekete, Poornananda R. Gaddehosur, Joseph S. B. Mitchell, Valentin Polishchuk, and Jukka Suomela
Title:	Improved approximation algorithms for relay placement
Conference:	16th Annual European Symposium on Algorithms (ESA), Karlsruhe, Germany, September 2008
Proceedings:	Dan Halperin and Kurt Mehlhorn (Eds.): Algorithms – ESA 2008. 16th Annual European Symposium. Karlsruhe, Germany, September 15–17, 2008. Proceedings
	Lecture Notes in Computer Science, volume 5193 Springer, Berlin, Germany, 2008 ISBN: 978-3-540-87743-6 pages 356–367 doi:10.1007/978-3-540-87744-8_30
Links:	publisher’s version · authors’ version © Springer 2008
	conference · proceedings · series · DBLP
Abstract:	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.

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.