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.
Bonifaci, V., Korteweg, P., Marchetti Spaccamela, A., & Stougie, L. (2008). An approximation algorithm for the Wireless Gathering Problem. Operations Research Letters, 36(5), 605-608. https://doi.org/10.1016/j.orl.2008.06.001