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 -