@inbook{d5d4913dd0634edbb49ad3978c36e9de,

title = "Polylogarithmic inapproximability of the radio broadcast problem (Extended abstract)",

abstract = "We prove that there exists a universal constant c > 0 such that the Radio Broadcast problem admits no additive c · log2 n-approximation, unless NP ⊆ BPTIME(nO(log log n)). For graphs of at most logarithmic radius, an O(log2 n) additive approximation algorithm is known, hence our lower bound is tight. To the best of our knowledge, this is the first tight additive polylogarithmic approximation result.",

author = "Michael Elkin and Guy Kortsarz",

year = "2004",

doi = "10.1007/978-3-540-27821-4_10",

language = "English (US)",

isbn = "3540228942",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "105--116",

editor = "Klaus Jansen and Sanjeev Khanna and Rolim, {Jose D. P.} and Dana Ron",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

address = "Germany",

}