Minimizing average flow time in sensor data gathering

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

Building on previous work [Bonifaci et al., Minimizing flow time in the wireless gathering problem, STACS 2008] we study data gathering in a wireless network through multi-hop communication with the objective to minimize the average flow time of a data packet. We show that for any ¿ ¿ (0, 1) the problem is NP-hard to approximate within a factor better than O(m1-¿), where m is the number of data packets. On the other hand, we give an online polynomial time algorithm that we analyze using resource augmentation. We show that the algorithm has average flow time bounded by that of an optimal solution when the clock speed of the algorithm is increased by a factor of five. As a byproduct of the analysis we obtain a 5-approximation algorithm for the problem of minimizing the average completion time of data packets.
Original languageEnglish
Title of host publicationAlgorithmic Aspects of Wireless Sensor Networks (4th International Workshop, Algosensors 2008, Reykjavik, Iceland, July 12, 2008, Revised Selected Papers)
EditorsS.P. Fekete
Place of PublicationBerlin
PublisherSpringer
Pages18-29
ISBN (Print)978-3-540-92861-4
DOIs
Publication statusPublished - 2008

Publication series

NameLecture Notes in Computer Science
Volume5389
ISSN (Print)0302-9743

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

Cite this