2026-07-22T16:01:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1338 2024-03-06T10:32:57Z ddc:004 open_access

Minimizing Flow Time in the Wireless Gathering Problem Bonifaci, Vincenzo Korteweg, Peter Marchetti-Spaccamela, Alberto Stougie, Leen Wireless networks data gathering approximation algorithms distributed algorithms 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 $Omega(m^{1/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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vincenzo Bonifaci and Peter Korteweg and Alberto Marchetti-Spaccamela and Leen Stougie 2008 Is Part Of LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2008.1338 urn:nbn:de:0030-drops-13381 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1338 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode