TY - GEN

T1 - Minimizing average flow time in sensor data gathering

AU - Bonifaci, V.

AU - Korteweg, P.

AU - Marchetti Spaccamela, A.

AU - Stougie, L.

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-540-92862-1_3

DO - 10.1007/978-3-540-92862-1_3

M3 - Conference contribution

SN - 978-3-540-92861-4

T3 - Lecture Notes in Computer Science

SP - 18

EP - 29

BT - Algorithmic Aspects of Wireless Sensor Networks (4th International Workshop, Algosensors 2008, Reykjavik, Iceland, July 12, 2008, Revised Selected Papers)

A2 - Fekete, S.P.

PB - Springer

CY - Berlin

ER -