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.
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].
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/380498
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 18
  • ???jsp.display-item.citation.isi??? 19
social impact