The Wireless Gathering Problem is to rind 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. (c) 2008 Elsevier B.V. All rights reserved.
An approximation algorithm for the wireless gathering problem / Bonifaci, Vincenzo; Peter, Korteweg; MARCHETTI SPACCAMELA, Alberto; Stougie, Leen. - In: OPERATIONS RESEARCH LETTERS. - ISSN 0167-6377. - 36:5(2008), pp. 605-608. [10.1016/j.orl.2008.06.001]
An approximation algorithm for the wireless gathering problem
BONIFACI, VINCENZO;MARCHETTI SPACCAMELA, Alberto;
2008
Abstract
The Wireless Gathering Problem is to rind 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. (c) 2008 Elsevier B.V. All rights reserved.File allegati a questo prodotto
| File | Dimensione | Formato | |
|---|---|---|---|
|
VE_2008_11573-361891.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
628.65 kB
Formato
Adobe PDF
|
628.65 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
