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 -