Sökning: id:"swepub:oai:DiVA.org:liu-127756" >
Improved Approximat...
Improved Approximation Algorithms for Relay Placement
-
- Efrat, Alon (författare)
- University of Arizona, AZ 85721 USA
-
- Fekete, Sandor P. (författare)
- Braunschweig University of Technology, Germany; TU Braunschweig, Germany
-
- Mitchell, Joseph S. B. (författare)
- SUNY Stony Brook, NY 11794 USA
-
visa fler...
-
- Polishchuk, Valentin (författare)
- Linköpings universitet,Kommunikations- och transportsystem,Tekniska fakulteten
-
- Suomela, Jukka (författare)
- Aalto University, Finland
-
visa färre...
-
(creator_code:org_t)
- 2015-12-31
- 2016
- Engelska.
-
Ingår i: ACM Transactions on Algorithms. - : ACM Press. - 1549-6325 .- 1549-6333. ; 12:2, s. 20-
- Relaterad länk:
-
http://arxiv.org/pdf...
-
visa fler...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- TEKNIK OCH TEKNOLOGIER -- Samhällsbyggnadsteknik (hsv//swe)
- ENGINEERING AND TECHNOLOGY -- Civil Engineering (hsv//eng)
Nyckelord
- Wireless networks; relays; sensor networks; approximation algorithms; Steiner minimum spanning tree; polynomial-time approximation scheme (PTAS)
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas