An approximation algorithm for the Wireless Gathering Problem

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

12 Citaten (Scopus)

Samenvatting

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.
Originele taal-2Engels
TitelAlgorithm Theory - SWAT 2006 (Proceedings 10th Scandinavian Workshop, Riga, Latvia, July 6-8, 2006)
RedacteurenL. Arge, R. Freivalds
Plaats van productieBerlin
UitgeverijSpringer
Pagina's328-338
ISBN van geprinte versie3-540-35753-X
DOI's
StatusGepubliceerd - 2006

Publicatie series

NaamLecture Notes in Computer Science
Volume4059
ISSN van geprinte versie0302-9743

Vingerafdruk Duik in de onderzoeksthema's van 'An approximation algorithm for the Wireless Gathering Problem'. Samen vormen ze een unieke vingerafdruk.

Citeer dit