Minimizing Flow Time in the Wireless Gathering Problem
2008
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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
18
References
2
Citations
NaN
KQI