TY - JOUR
T1 - An approximation algorithm for the Wireless Gathering Problem
AU - Bonifaci, V.
AU - Korteweg, P.
AU - Marchetti Spaccamela, A.
AU - Stougie, L.
PY - 2008
Y1 - 2008
N2 - The Wireless Gathering Problem is to find an interference-free schedule for data gathering in a wireless network in minimum time. We present a 4-approximate polynomial-time on-line algorithm for this NP-hard problem. We show that no shortest path following algorithm can have an approximation ratio better than 4.
AB - The Wireless Gathering Problem is to find an interference-free schedule for data gathering in a wireless network in minimum time. We present a 4-approximate polynomial-time on-line algorithm for this NP-hard problem. We show that no shortest path following algorithm can have an approximation ratio better than 4.
U2 - 10.1016/j.orl.2008.06.001
DO - 10.1016/j.orl.2008.06.001
M3 - Article
SN - 0167-6377
VL - 36
SP - 605
EP - 608
JO - Operations Research Letters
JF - Operations Research Letters
IS - 5
ER -