de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

Minimizing Flow Time in the Wireless Gathering Problem

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44160

Bonifaci,  Vincenzo
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Bonifaci, V., Korteweg, P., Marchetti-Spaccamela, A., & Stougie, L. (2011). Minimizing Flow Time in the Wireless Gathering Problem. ACM Transactions on Algorithms, 7(3): 33, pp. 33:1-33:20. doi:10.1145/1978782.1978788.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0010-1254-9
Zusammenfassung
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-\epsilon})$ for any $0<\epsilon<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.