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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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) Published
Resource type
Text
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
Identifiers
URN: urn:nbn:se:liu:diva-127756DOI: 10.1145/2814938ISI: 000373905400008OAI: oai:DiVA.org:liu-127756DiVA: diva2:927482
Note

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

Altmetric score

Total: 103 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf