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. © 2008 Elsevier B.V. All rights reserved.
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 [10.1016/j.orl.2008.06.001].
An approximation algorithm for the wireless gathering problem
Bonifaci V.
;
2008-01-01
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. © 2008 Elsevier B.V. All rights reserved.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
gathering-orl.pdf
accesso aperto
Tipologia:
Documento in Pre-print
Licenza:
DRM non definito
Dimensione
123.29 kB
Formato
Adobe PDF
|
123.29 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
