Logarithmic inapproximability of the radio broadcast problem

DOI10.1016/J.JALGOR.2003.11.004MaRDI QIDQ4828562zbMATH OpenOpenAlexFDO

Authors Michael Elkin, Guy Kortsarz

Publication date 23 November 2004

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jalgor.2003.11.004

zbMATH Keywords

set-cover problemlabel-cover problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Communication networks in operations research (90B18)

Recommendations

• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Polylogarithmic Additive Inapproximability of the Radio Broadcast Problem
• scientific article; zbMATH DE number 1670545
• An $\Omega(D\log (N/D))$ Lower Bound for Broadcast in Radio Networks
• A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem

Cited in

(11)

• GATHERING RADIO MESSAGES IN THE PATH
• Faster communication in known topology radio networks
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Optimal gathering protocols on paths under interference constraints
• Optimal deterministic broadcasting in known topology radio networks
• Polylogarithmic Additive Inapproximability of the Radio Broadcast Problem
• Many-to-many communication in radio networks
• Improved algorithm for broadcast scheduling of minimal latency in wireless ad hoc networks
• Time-efficient broadcast in radio networks
• A lower bound for radio broadcast
• Reception capacity: definitions, game theory and hardness

This page was built for publication: Logarithmic inapproximability of the radio broadcast problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4828562)