| Article ID: | iaor20102884 |
| Volume: | 36 |
| Issue: | 5 |
| Start Page Number: | 605 |
| End Page Number: | 608 |
| Publication Date: | Sep 2008 |
| Journal: | Operations Research Letters |
| Authors: | Stougie Leen, Korteweg Peter, Bonifaci Vincenzo, Marchetti-Spaccamela Alberto |
| Keywords: | networks |
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.