Improved Approximation Algorithms for Relay Placement

Tutkimustuotos: Lehtiartikkelivertaisarvioitu

Standard

Improved Approximation Algorithms for Relay Placement. / Efrat, Alon; Fekete, Sandor P.; Mitchell, Joseph S. B.; Polishchuk, Valentin; Suomela, Jukka.

julkaisussa: ACM Transactions on Algorithms, Vuosikerta 12, Nro 2, 20, 02.2016.

Tutkimustuotos: Lehtiartikkelivertaisarvioitu

Harvard

Efrat, A, Fekete, SP, Mitchell, JSB, Polishchuk, V & Suomela, J 2016, 'Improved Approximation Algorithms for Relay Placement', ACM Transactions on Algorithms, Vuosikerta. 12, Nro 2, 20. https://doi.org/10.1145/2814938

APA

Efrat, A., Fekete, S. P., Mitchell, J. S. B., Polishchuk, V., & Suomela, J. (2016). Improved Approximation Algorithms for Relay Placement. ACM Transactions on Algorithms, 12(2), [20]. https://doi.org/10.1145/2814938

Vancouver

Author

Efrat, Alon ; Fekete, Sandor P. ; Mitchell, Joseph S. B. ; Polishchuk, Valentin ; Suomela, Jukka. / Improved Approximation Algorithms for Relay Placement. Julkaisussa: ACM Transactions on Algorithms. 2016 ; Vuosikerta 12, Nro 2.

Bibtex - Lataa

@article{17b928d1d8b44c059c391c59d5f65383,
title = "Improved Approximation Algorithms for Relay Placement",
abstract = "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.",
keywords = "Wireless networks, relays, sensor networks, approximation algorithms, Steiner minimum spanning tree, polynomial-time approximation scheme (PTAS), WIRELESS SENSOR NETWORKS, NODE PLACEMENT, STEINER POINTS, MINIMUM NUMBER, CONNECTIVITY, TREES, SCHEMES",
author = "Alon Efrat and Fekete, {Sandor P.} and Mitchell, {Joseph S. B.} and Valentin Polishchuk and Jukka Suomela",
note = "VK: Suomela, J.; HIIT",
year = "2016",
month = "2",
doi = "10.1145/2814938",
language = "English",
volume = "12",
journal = "ACM Transactions on Algorithms",
issn = "1549-6325",
number = "2",

}

RIS - Lataa

TY - JOUR

T1 - Improved Approximation Algorithms for Relay Placement

AU - Efrat, Alon

AU - Fekete, Sandor P.

AU - Mitchell, Joseph S. B.

AU - Polishchuk, Valentin

AU - Suomela, Jukka

N1 - VK: Suomela, J.; HIIT

PY - 2016/2

Y1 - 2016/2

N2 - 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.

AB - 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.

KW - Wireless networks

KW - relays

KW - sensor networks

KW - approximation algorithms

KW - Steiner minimum spanning tree

KW - polynomial-time approximation scheme (PTAS)

KW - WIRELESS SENSOR NETWORKS

KW - NODE PLACEMENT

KW - STEINER POINTS

KW - MINIMUM NUMBER

KW - CONNECTIVITY

KW - TREES

KW - SCHEMES

UR - http://dl.acm.org/citation.cfm?id=2814938

U2 - 10.1145/2814938

DO - 10.1145/2814938

M3 - Article

VL - 12

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

SN - 1549-6325

IS - 2

M1 - 20

ER -

ID: 2039207