2008
An approximation algorithm for the Wireless Gathering Problem
Publication
Publication
Operations Research Letters , Volume 36 - Issue 5 p. 605- 608
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.
| Additional Metadata | |
|---|---|
| , , | |
| North-Holland | |
| Operations Research Letters | |
| Organisation | Networks and Optimization |
|
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. |
|