TY - GEN
T1 - Radio aggregation scheduling
AU - Gandhi, Rajiv
AU - Halldórsson, Magnús M.
AU - Konrad, Christian
AU - Kortsarz, Guy
AU - Oh, Hoon
N1 - Funding Information:
Gandhi and Oh are partly supported by NSF grants CCF 1218620 and CCF 1433220. Halldorsson and Konrad are supported by Icelandic Research Fund grantof- excellence no. 120032011. Kortsarz is partly supported by NSF grant CCF 1218620.
Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - 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 (Formula presented.)-approximation algorithm, where d̅ is the average degree and n the number of vertices in the graph, and show that the problem is Ω(n1-ε)-hard (and Ω((dn)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 O(log n)-approximation in interval graphs
AB - 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 (Formula presented.)-approximation algorithm, where d̅ is the average degree and n the number of vertices in the graph, and show that the problem is Ω(n1-ε)-hard (and Ω((dn)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 O(log n)-approximation in interval graphs
UR - http://www.scopus.com/inward/record.url?scp=84955249412&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84955249412&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-28472-9_13
DO - 10.1007/978-3-319-28472-9_13
M3 - Conference contribution
AN - SCOPUS:84955249412
SN - 9783319284712
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 169
EP - 182
BT - Algorithms for Sensor Systems - 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2015, Revised Selected Papers
A2 - Römer, Kay
A2 - Wattenhofer, Roger
A2 - Gąsieniec, Leszek Antoni
A2 - Bose, Prosenjit
PB - Springer Verlag
T2 - 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2015
Y2 - 17 September 2015 through 18 September 2015
ER -