An approximation algorithm for the Wireless Gathering Problem

V. Bonifaci, P. Korteweg, A. Marchetti Spaccamela, L. Stougie

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

11 Citations (Scopus)

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 languageEnglish
Title of host publicationAlgorithm Theory - SWAT 2006 (Proceedings 10th Scandinavian Workshop, Riga, Latvia, July 6-8, 2006)
EditorsL. Arge, R. Freivalds
Place of PublicationBerlin
PublisherSpringer
Pages328-338
ISBN (Print)3-540-35753-X
DOIs
Publication statusPublished - 2006

Publication series

NameLecture Notes in Computer Science
Volume4059
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