An approximation algorithm for the wireless gathering problem

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

    Research output: Contribution to JournalArticleAcademicpeer-review

    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. © 2008 Elsevier B.V. All rights reserved.
    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