We address the problem of efficient data gathering in a wireless network through multihop communication. We focus on two objectives related to flow times, that is, the times spent by data packets in the system: minimization of the maximum flow time and minimization of the average flow time of the packets. For both problems we prove that, unless P = NP, no polynomial-time algorithm can approximate the optimal solution within a factor less than Omega(m^{1-ε}) for any 0 < ε < 1, where m is the number of packets. We then assess the performance of two natural algorithms by proving that their cost remains within the optimal cost of the respective problem if we allow the algorithms to transmit data at a speed 5 times higher than that of the optimal solutions to which we compare them. © 2011 ACM.

Bonifaci, V., Korteweg, P., Marchetti-Spaccamela, A., Stougie, L. (2011). Minimizing flow time in the wireless gathering problem. ACM TRANSACTIONS ON ALGORITHMS, 7(3), 1-20 [10.1145/1978782.1978788].

Minimizing flow time in the wireless gathering problem

Bonifaci V.
;
2011-01-01

Abstract

We address the problem of efficient data gathering in a wireless network through multihop communication. We focus on two objectives related to flow times, that is, the times spent by data packets in the system: minimization of the maximum flow time and minimization of the average flow time of the packets. For both problems we prove that, unless P = NP, no polynomial-time algorithm can approximate the optimal solution within a factor less than Omega(m^{1-ε}) for any 0 < ε < 1, where m is the number of packets. We then assess the performance of two natural algorithms by proving that their cost remains within the optimal cost of the respective problem if we allow the algorithms to transmit data at a speed 5 times higher than that of the optimal solutions to which we compare them. © 2011 ACM.
2011
Bonifaci, V., Korteweg, P., Marchetti-Spaccamela, A., Stougie, L. (2011). Minimizing flow time in the wireless gathering problem. ACM TRANSACTIONS ON ALGORITHMS, 7(3), 1-20 [10.1145/1978782.1978788].
File in questo prodotto:
File Dimensione Formato  
gathering-talg-final.pdf

accesso aperto

Tipologia: Documento in Post-print
Licenza: DRM non definito
Dimensione 275.2 kB
Formato Adobe PDF
275.2 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/381257
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 7
social impact