|
|||||
|
|
An approximation algorithm for the wireless gathering problem |
|
| Authors: | Vincenzo Bonifaci Peter Korteweg Alberto Marchetti-Spaccamela Leen Stougie |
| Affiliation: | aDepartment of Electrical and Information Engineering, University of L’Aquila, Italy;bDepartment of Computer and Systems Science, University of Rome “La Sapienza”, Italy;cDepartment of Mathematics and Computer Science, TU Eindhoven, The Netherlands;dCWI Amsterdam, The Netherlands |
| Abstract: | 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. |
| Keywords: | Wireless networks Data gathering Approximation algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ | |