LIPIcs.STACS.2008.1338.pdf
- Filesize: 184 kB
- 12 pages
Document
Minimizing Flow Time in the Wireless Gathering Problem
Authors
-
Part of:
Volume:
25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NoDerivs 3.0 Unported license
- Publication Date: 2008-02-06
Cite As Get BibTex
Vincenzo Bonifaci, Peter Korteweg, Alberto Marchetti-Spaccamela, and Leen Stougie. Minimizing Flow Time in the Wireless Gathering Problem. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 109-120, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/LIPIcs.STACS.2008.1338
Abstract
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.
Subject Classification
Keywords
- Wireless networks
- data gathering
- approximation algorithms
- distributed algorithms
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads