Minimizing flow time in the wireless gathering problem

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

Research output: Contribution to journalArticleAcademicpeer-review

12 Citations (Scopus)


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
Issue number3
Publication statusPublished - 2011


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

Cite this