An approximation algorithm for the Wireless Gathering Problem

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

Research output: Contribution to journalArticleAcademicpeer-review

18 Citations (Scopus)
1 Downloads (Pure)


The Wireless Gathering Problem is to find an interference-free schedule for data gathering in a wireless network in minimum time. We present a 4-approximate polynomial-time on-line algorithm for this NP-hard problem. We show that no shortest path following algorithm can have an approximation ratio better than 4.
Original languageEnglish
Pages (from-to)605-608
JournalOperations Research Letters
Issue number5
Publication statusPublished - 2008


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

Cite this