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 -