An approximation algorithm for the Wireless Gathering Problem

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

Research output: Contribution to journalArticleAcademicpeer-review

17 Citations (Scopus)
1 Downloads (Pure)

Abstract

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
Volume36
Issue number5
DOIs
Publication statusPublished - 2008

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. (2008). An approximation algorithm for the Wireless Gathering Problem. Operations Research Letters, 36(5), 605-608. https://doi.org/10.1016/j.orl.2008.06.001