# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Minimizing Flow Time in the Wireless Gathering Problem

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Bonifaci, V., Korteweg, P., Marchetti-Spaccamela, A., & Stougie, L. (2011). Minimizing
Flow Time in the Wireless Gathering Problem.* ACM Transactions on Algorithms,* *7*(3):
33, pp. 33:1-33:20. doi:10.1145/1978782.1978788.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0010-1254-9

##### Abstract

We address the problem of efficient data gathering in a wireless network
through multihop communication. We focus on two objectives related to flow
times, that is, the times spent by data packets in the system: minimization of
the maximum flow time and minimization of the average flow time of the packets.
For both problems we prove that, unless P=NP, no polynomial-time algorithm can
approximate the optimal solution within a factor less than
$\Omega(m^{1-\epsilon})$ for any $0<\epsilon<1$, where $m$ is the number of
packets. We then assess the performance of two natural algorithms by proving
that their cost remains within the optimal cost of the respective problem if we
allow the algorithms to transmit data at a speed 5 times higher than that of
the optimal solutions to which we compare them.