### Abstract

The Wireless Gathering Problem is to find a schedule for
data gathering in a wireless static network. The problem is to gather a
set of messages from the nodes in the network at which they originate
to a central node, representing a powerful base station. The objective
is to minimize the time to gather all messages. The sending pattern or
schedule should avoid interference of radio signals, which distinguishes
the problem from wired networks.
We study the Wireless Gathering Problem from a combinatorial optimization
point of view in a centralized setting. This problem is known
to be NP-hard when messages have no release time. We consider the
more general case in which messages may be released over time. For this
problem we present a polynomial-time on-line algorithm which gives a
4-approximation. We also show that within the class of shortest path
following algorithms no algorithm can have approximation ratio better
than 4. We also formulate some challenging open problems concerning
complexity and approximability for variations of the problem.

Original language | English |
---|---|

Title of host publication | Algorithm Theory - SWAT 2006 (Proceedings 10th Scandinavian Workshop, Riga, Latvia, July 6-8, 2006) |

Editors | L. Arge, R. Freivalds |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 328-338 |

ISBN (Print) | 3-540-35753-X |

DOIs | |

Publication status | Published - 2006 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Volume | 4059 |

ISSN (Print) | 0302-9743 |

## Fingerprint Dive into the research topics of 'An approximation algorithm for the Wireless Gathering Problem'. Together they form a unique fingerprint.

## Cite this

Bonifaci, V., Korteweg, P., Marchetti Spaccamela, A., & Stougie, L. (2006). An approximation algorithm for the Wireless Gathering Problem. In L. Arge, & R. Freivalds (Eds.),

*Algorithm Theory - SWAT 2006 (Proceedings 10th Scandinavian Workshop, Riga, Latvia, July 6-8, 2006)*(pp. 328-338). (Lecture Notes in Computer Science; Vol. 4059). Berlin: Springer. https://doi.org/10.1007/11785293_31