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.

Bonifaci, V., Korteweg, P., Marchetti-Spaccamela, A., Stougie, L. (2008). Minimizing flow time in the wireless gathering problem. In 25th International Symposium on Theoretical Aspects of Computer Science (pp.109-120). Dagstuhl : IBFI Schloss Dagstuhl [10.4230/LIPIcs.STACS.2008.1338].

Minimizing flow time in the wireless gathering problem

Bonifaci V.;
2008-01-01

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
978-3-939897-06-4
Bonifaci, V., Korteweg, P., Marchetti-Spaccamela, A., Stougie, L. (2008). Minimizing flow time in the wireless gathering problem. In 25th International Symposium on Theoretical Aspects of Computer Science (pp.109-120). Dagstuhl : IBFI Schloss Dagstuhl [10.4230/LIPIcs.STACS.2008.1338].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/380494
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 0
social impact