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
المعرِّفات الرقمية للأشياء	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, اليونان المدة: ١٧ سبتمبر ٢٠١٥ → ١٨ سبتمبر ٢٠١٥

سلسلة المنشورات

الاسم	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت	9536
رقم المعيار الدولي للدوريات (المطبوع)	0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)	1611-3349

!!Conference

!!Conference	11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2015
الدولة/الإقليم	اليونان
المدينة	Patras
المدة	١٧/٠٩/١٥ → ١٨/٠٩/١٥

ملاحظة ببليوغرافية

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 وآخرون. / 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, اليونان, ١٧/٠٩/١٥. https://doi.org/10.1007/978-3-319-28472-9_13

Radio aggregation scheduling. / Gandhi, Rajiv; Halldórsson, Magnús M.; Konrad, Christian وآخرون.
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

ملخص

سلسلة المنشورات

!!Conference

ملاحظة ببليوغرافية

الوصول إلى المستند

الملفات والروابط الأخرى

بصمة

قم بذكر هذا