liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Improved Approximation Algorithms for Relay Placement
University of Arizona, AZ 85721 USA.
Braunschweig University of Technology, Germany; TU Braunschweig, Germany.
SUNY Stony Brook, NY 11794 USA.
Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, Faculty of Science & Engineering.
Show others and affiliations
2016 (English)In: ACM Transactions on Algorithms, ISSN 1549-6325, E-ISSN 1549-6333, Vol. 12, no 2, 20- p.Article in journal (Refereed) PublishedText
Abstract [en]

In the relay placement problem, the input is a set of sensors and a number r >= 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 polynomial-time approximation scheme (PTAS) for the two-tier version. We also show that the one-tier version admits no PTAS, assuming P not equal NP.

Place, publisher, year, edition, pages
ACM Press, 2016. Vol. 12, no 2, 20- p.
Keyword [en]
Wireless networks; relays; sensor networks; approximation algorithms; Steiner minimum spanning tree; polynomial-time approximation scheme (PTAS)
National Category
Civil Engineering
URN: urn:nbn:se:liu:diva-127756DOI: 10.1145/2814938ISI: 000373905400008OAI: diva2:927482

Funding Agencies|EU project FRONTS (FP7) [215270]; National Science Foundation [CCF-0431030, CCF-0528209, CCF-0729019, CCF-1018388, CCF-1540890, 0348000]; NASA Ames; Metron Aviation; Sandia National Labs; Academy of Finland [116547]; Helsinki Graduate School in Computer Science and Engineering (Hecse); Foundation of Nokia Corporation

Available from: 2016-05-12 Created: 2016-05-12 Last updated: 2016-05-12

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Polishchuk, Valentin
By organisation
Communications and Transport SystemsFaculty of Science & Engineering
In the same journal
ACM Transactions on Algorithms
Civil Engineering

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 60 hits
ReferencesLink to record
Permanent link

Direct link