Radio aggregation scheduling

Rajiv Gandhi; Magnús M. Halldórsson; Christian Konrad; Guy Kortsarz; Hoon Oh

doi:10.1007/978-3-319-28472-9_13

Radio aggregation scheduling

Rajiv Gandhi
, Magnús M. Halldórsson
, Christian Konrad
, Guy Kortsarz
, Hoon Oh

פרסום מחקרי: פרק בספר / בדוח / בכנס › פרסום בספר כנס › ביקורת עמיתים

תקציר

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 Ω(n^1-ε)-hard (and Ω((dn)^1/2-ε)-hard) to approximate even on bipartite graphs, for any ε > 0, rendering our algorithm essentially optimal.

שפה מקורית	אנגלית
כותר פרסום המארח	Algorithms for Sensor Systems - 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2015, Revised Selected Papers
עורכים	Kay Römer, Roger Wattenhofer, Leszek Antoni Gąsieniec, Prosenjit Bose
מוציא לאור	Springer Verlag
עמודים	169-182
מספר עמודים	14
מסת"ב (מודפס)	9783319284712
מזהי עצם דיגיטלי (DOIs)	https://doi.org/10.1007/978-3-319-28472-9_13
סטטוס פרסום	פורסם - 2015
פורסם באופן חיצוני	כן
אירוע	11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2015 - Patras, יוון משך הזמן: 17 ספט׳ 2015 → 18 ספט׳ 2015

סדרות פרסומים

שם	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך	9536
ISSN (מודפס)	0302-9743
ISSN (אלקטרוני)	1611-3349

כנס

כנס	11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2015
מדינה/אזור	יוון
עיר	Patras
תקופה	17/09/15 → 18/09/15

הערה ביבליוגרפית

Publisher Copyright:
© Springer International Publishing Switzerland 2015.

גישה למסמך

10.1007/978-3-319-28472-9_13

קבצים וקישורים אחרים

Link to publication in Scopus

פורמט ציטוט ביבליוגרפי

Gandhi, R., Halldórsson, M. M., Konrad, C., Kortsarz, G., & Oh, H. (2015). Radio aggregation scheduling. ב- K. Römer, R. Wattenhofer, L. A. Gąsieniec, & P. Bose (עורכים), Algorithms for Sensor Systems - 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2015, Revised Selected Papers (עמודים 169-182). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); כרך 9536). Springer Verlag. https://doi.org/10.1007/978-3-319-28472-9_13

Gandhi, Rajiv ; Halldórsson, Magnús M. ; Konrad, Christian et al. / Radio aggregation scheduling. Algorithms for Sensor Systems - 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2015, Revised Selected Papers. עורך / Kay Römer ; Roger Wattenhofer ; Leszek Antoni Gąsieniec ; Prosenjit Bose. Springer Verlag, 2015. עמודים 169-182 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{137a1d13356e4ad4ac7aa41c7e7ec257,

title = "Radio aggregation scheduling",

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 (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.",

author = "Rajiv Gandhi and Halld{\'o}rsson, \{Magn{\'u}s M.\} and Christian Konrad and Guy Kortsarz and Hoon Oh",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2015 ; Conference date: 17-09-2015 Through 18-09-2015",

year = "2015",

doi = "10.1007/978-3-319-28472-9\_13",

language = "אנגלית",

isbn = "9783319284712",

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

publisher = "Springer Verlag",

pages = "169--182",

editor = "Kay R{\"o}mer and Roger Wattenhofer and G{\c a}sieniec, \{Leszek Antoni\} and Prosenjit Bose",

booktitle = "Algorithms for Sensor Systems - 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2015, Revised Selected Papers",

address = "גרמניה",

}

Gandhi, R, Halldórsson, MM, Konrad, C, Kortsarz, G & Oh, H 2015, Radio aggregation scheduling. ב- K Römer, R Wattenhofer, LA Gąsieniec & P Bose (עורכים), Algorithms for Sensor Systems - 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2015, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), כרך 9536, Springer Verlag, עמודים 169-182, 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2015, Patras, יוון, 17/09/15. https://doi.org/10.1007/978-3-319-28472-9_13

Radio aggregation scheduling. / Gandhi, Rajiv; Halldórsson, Magnús M.; Konrad, Christian et al.
Algorithms for Sensor Systems - 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2015, Revised Selected Papers. עורך / Kay Römer; Roger Wattenhofer; Leszek Antoni Gąsieniec; Prosenjit Bose. Springer Verlag, 2015. עמוד 169-182 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); כרך 9536).

פרסום מחקרי: פרק בספר / בדוח / בכנס › פרסום בספר כנס › ביקורת עמיתים

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 - 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.

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.

UR - https://www.scopus.com/pages/publications/84955249412

U2 - 10.1007/978-3-319-28472-9_13

DO - 10.1007/978-3-319-28472-9_13

M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???

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 -

Gandhi R, Halldórsson MM, Konrad C, Kortsarz G, Oh H. Radio aggregation scheduling. ב- Römer K, Wattenhofer R, Gąsieniec LA, Bose P, עורכים, Algorithms for Sensor Systems - 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2015, Revised Selected Papers. Springer Verlag. 2015. עמוד 169-182. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-28472-9_13

Radio aggregation scheduling

תקציר

סדרות פרסומים

כנס

הערה ביבליוגרפית

גישה למסמך

קבצים וקישורים אחרים

טביעת אצבע

פורמט ציטוט ביבליוגרפי