Radio aggregation scheduling

R. Gandhi, M.M. Halldórsson, C. Konrad, G. Kortsarz, H. Oh

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

We consider the aggregation problem in radio networks: find a spanning tree in a given graph and a conflict-free schedule of the edges so as to minimize the latency of the computation. While a large body of literature exists on this and related problems, we give the first approximation results in graphs that are not induced by unit ranges in the plane. We give a polynomial-time Õ (𝑑⎯⎯⎯𝑛‾‾‾√)
-approximation algorithm, where 𝑑⎯⎯⎯
is the average degree and n the number of vertices in the graph, and show that the problem is Ω(𝑛1−𝜖)
-hard (and Ω((𝑑⎯⎯⎯𝑛)1/2−𝜖)
-hard) to approximate even on bipartite graphs, for any 𝜖>0
, rendering our algorithm essentially optimal. We target geometrically defined graph classes, and in particular obtain a 𝑂(log𝑛)
-approximation in interval graphs.
Original languageEnglish
Title of host publicationAlgorithms for Sensor Systems
Subtitle of host publication11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2015, Patras, Greece, September 17-18, 2015, Revised Selected Papers
PublisherSpringer, Cham
Pages169-182
ISBN (Electronic)978-3-319-28472-9
ISBN (Print)978-3-319-28471-2
DOIs
Publication statusPublished - 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Fingerprint

Dive into the research topics of 'Radio aggregation scheduling'. Together they form a unique fingerprint.

Cite this