Improved approximation algorithms for relay placement

Alon Efrat; Sándor P. Fekete; Joseph S.B. Mitchell; Valentin Polishchuk; Jukka Suomela

doi:10.1145/2814938

Improved approximation algorithms for relay placement

Alon Efrat, Sándor P. Fekete, Joseph S.B. Mitchell, Valentin Polishchuk, Jukka Suomela

Computer Science

Research output: Contribution to journal › Article › peer-review

8 Scopus citations

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 ≠ NP.

Original language	English (US)
Article number	20
Journal	ACM Transactions on Algorithms
Volume	12
Issue number	2
DOIs	https://doi.org/10.1145/2814938
State	Published - Dec 1 2015

Keywords

Approximation algorithms
Polynomial-time approximation scheme (PTAS)
Relays
Sensor networks
Steiner minimum spanning tree
Wireless networks

ASJC Scopus subject areas

Mathematics (miscellaneous)

Access to Document

10.1145/2814938

Cite this

@article{ac34235892c04a1a98e4179deefbc084,

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 ≠ NP.",

keywords = "Approximation algorithms, Polynomial-time approximation scheme (PTAS), Relays, Sensor networks, Steiner minimum spanning tree, Wireless networks",

author = "Alon Efrat and Fekete, {S{\'a}ndor P.} and Mitchell, {Joseph S.B.} and Valentin Polishchuk and Jukka Suomela",

note = "Publisher Copyright: Copyright {\textcopyright} 2015 ACM.",

year = "2015",

month = dec,

day = "1",

doi = "10.1145/2814938",

language = "English (US)",

volume = "12",

journal = "ACM Transactions on Algorithms",

issn = "1549-6325",

publisher = "Association for Computing Machinery (ACM)",

number = "2",

}

TY - JOUR

T1 - Improved approximation algorithms for relay placement

AU - Efrat, Alon

AU - Fekete, Sándor P.

AU - Mitchell, Joseph S.B.

AU - Polishchuk, Valentin

AU - Suomela, Jukka

PY - 2015/12/1

Y1 - 2015/12/1

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 ≠ 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 ≠ NP.

KW - Approximation algorithms

KW - Polynomial-time approximation scheme (PTAS)

KW - Relays

KW - Sensor networks

KW - Steiner minimum spanning tree

KW - Wireless networks

UR - http://www.scopus.com/inward/record.url?scp=84954313620&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84954313620&partnerID=8YFLogxK

U2 - 10.1145/2814938

DO - 10.1145/2814938

M3 - Article

AN - SCOPUS:84954313620

SN - 1549-6325

VL - 12

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 2

M1 - 20

ER -

Improved approximation algorithms for relay placement

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this