Minimizing flow time in the wireless gathering problem

V. Bonifaci, P. Korteweg, A. Marchetti Spaccamela, L. Stougie

Research output: Contribution to journalArticleAcademicpeer-review

9 Citations (Scopus)

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 O(m^{1-e}) for any 0
Original languageEnglish
Article number33
Pages (from-to)33-1/20
Number of pages20
JournalACM Transactions on Algorithms
Volume7
Issue number3
DOIs
Publication statusPublished - 2011

Fingerprint Dive into the research topics of 'Minimizing flow time in the wireless gathering problem'. Together they form a unique fingerprint.

  • Cite this

    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-1/20. [33]. https://doi.org/10.1145/1978782.1978788