We address the problem of efficient data gathering in a wireless network through multi-hop communication. We focus on the objective of minimizing the maximum flow time of a data packet. We prove that no polynomial time algorithm for this problem can have approximation ratio less than Ω(m1/3) when m packets have to be transmitted, unless P = NP. We then use resource augmentation to assess the performance of a FIFO-like strategy. We prove that this strategy is 5-speed optimal, i.e., its cost remains within the optimal cost if we allow the algorithm to transmit data at a speed 5 times higher than that of the optimal solution we compare to.

Minimizing Flow Time in the Wireless Gathering Problem / Bonifaci, Vincenzo; Peter, Korteweg; MARCHETTI SPACCAMELA, Alberto; Leen, Stougie. - (2008), pp. 109-120. (Intervento presentato al convegno 25th Symp. on Theoretical Aspects of Computer Science tenutosi a Bordeaux; France nel February 21-23, 2008) [10.4230/LIPIcs.STACS.2008.1338].

Minimizing Flow Time in the Wireless Gathering Problem

BONIFACI, VINCENZO;MARCHETTI SPACCAMELA, Alberto;
2008

Abstract

We address the problem of efficient data gathering in a wireless network through multi-hop communication. We focus on the objective of minimizing the maximum flow time of a data packet. We prove that no polynomial time algorithm for this problem can have approximation ratio less than Ω(m1/3) when m packets have to be transmitted, unless P = NP. We then use resource augmentation to assess the performance of a FIFO-like strategy. We prove that this strategy is 5-speed optimal, i.e., its cost remains within the optimal cost if we allow the algorithm to transmit data at a speed 5 times higher than that of the optimal solution we compare to.
2008
25th Symp. on Theoretical Aspects of Computer Science
Approximation algorithms; Data gathering; Distributed algorithms
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Minimizing Flow Time in the Wireless Gathering Problem / Bonifaci, Vincenzo; Peter, Korteweg; MARCHETTI SPACCAMELA, Alberto; Leen, Stougie. - (2008), pp. 109-120. (Intervento presentato al convegno 25th Symp. on Theoretical Aspects of Computer Science tenutosi a Bordeaux; France nel February 21-23, 2008) [10.4230/LIPIcs.STACS.2008.1338].
File allegati a questo prodotto
File Dimensione Formato  
VE_2008_11573-366685.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 274.33 kB
Formato Adobe PDF
274.33 kB Adobe PDF   Contatta l'autore

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/11573/366685
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 0
social impact