TY - GEN

T1 - Minimizing flow time in the wireless gathering problem

AU - Bonifaci, Vincenzo

AU - Korteweg, Peter

AU - Marchetti-Spaccamela, Alberto

AU - Stougie, Leen

PY - 2008/1/1

Y1 - 2008/1/1

N2 - We address the problem of efficient data gathering in a wireless network through multi-hop communication. We focus on the objective of minimizing the maximum flow time of a data packet. We prove that no polynomial time algorithm for this problem can have approximation ratio less than Ω(m1/3) when m packets have to be transmitted, unless P = NP. We then use resource augmentation to assess the performance of a FIFO-like strategy. We prove that this strategy is 5-speed optimal, i.e., its cost remains within the optimal cost if we allow the algorithm to transmit data at a speed 5 times higher than that of the optimal solution we compare to.

AB - We address the problem of efficient data gathering in a wireless network through multi-hop communication. We focus on the objective of minimizing the maximum flow time of a data packet. We prove that no polynomial time algorithm for this problem can have approximation ratio less than Ω(m1/3) when m packets have to be transmitted, unless P = NP. We then use resource augmentation to assess the performance of a FIFO-like strategy. We prove that this strategy is 5-speed optimal, i.e., its cost remains within the optimal cost if we allow the algorithm to transmit data at a speed 5 times higher than that of the optimal solution we compare to.

KW - Approximation algorithms

KW - Data gathering

KW - Distributed algorithms

KW - Wireless networks

UR - http://www.scopus.com/inward/record.url?scp=45749124408&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=45749124408&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:45749124408

SN - 9783939897064

T3 - Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008

SP - 109

EP - 120

BT - Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008

PB - IBFI Schloss Dagstuhl

T2 - 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008

Y2 - 21 February 2008 through 23 February 2008

ER -