TY - GEN

T1 - Spanning trees with edge conflicts and wireless connectivity

AU - Halldórsson, Magnús M.

AU - Kortsarz, Guy

AU - Mitra, Pradipta

AU - Tonoyan, Tigran

N1 - Funding Information:
Funding The first and last authors are supported by grants nos. 152679-05 and 174484-05 from the Icelandic Research Fund. The second author is supported by NSF grant 1540547.
Funding Information:
The first and last authors are supported by grants nos. 152679-05 and 174484-05 from the Icelandic Research Fund. The second author is supported by NSF grant 1540547.
Publisher Copyright:
© 2018 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

PY - 2018/7/1

Y1 - 2018/7/1

N2 - We introduce the problem of finding a spanning tree along with a partition of the tree edges into fewest number of feasible sets, where constraints on the edges define feasibility. The motivation comes from wireless networking, where we seek to model the irregularities seen in actual wireless environments. Not all node pairs may be able to communicate, even if geographically close - thus, the available pairs are specified with a link graph L = (V, E). Also, signal attenuation need not follow a nice geometric formula - hence, interference is modeled by a conflict (hyper)graph C = (E, F) on the links. The objective is to maximize the e ciency of the communication, or equivalently, to minimize the length of a schedule of the tree edges in the form of a coloring. We find that in spite of all this generality, the problem can be approximated linearly in terms of a versatile parameter, the inductive independence of the interference graph. Specifically, we give a simple algorithm that attains a O(ρ log n)-approximation, where n is the number of nodes and ρ is the inductive independence, and show that near-linear dependence on ρ is also necessary. We also treat an extension to Steiner trees, modeling multicasting, and obtain a comparable result. Our results suggest that several canonical assumptions of geometry, regularity and “niceness” in wireless settings can sometimes be relaxed without a significant hit in algorithm performance.

AB - We introduce the problem of finding a spanning tree along with a partition of the tree edges into fewest number of feasible sets, where constraints on the edges define feasibility. The motivation comes from wireless networking, where we seek to model the irregularities seen in actual wireless environments. Not all node pairs may be able to communicate, even if geographically close - thus, the available pairs are specified with a link graph L = (V, E). Also, signal attenuation need not follow a nice geometric formula - hence, interference is modeled by a conflict (hyper)graph C = (E, F) on the links. The objective is to maximize the e ciency of the communication, or equivalently, to minimize the length of a schedule of the tree edges in the form of a coloring. We find that in spite of all this generality, the problem can be approximated linearly in terms of a versatile parameter, the inductive independence of the interference graph. Specifically, we give a simple algorithm that attains a O(ρ log n)-approximation, where n is the number of nodes and ρ is the inductive independence, and show that near-linear dependence on ρ is also necessary. We also treat an extension to Steiner trees, modeling multicasting, and obtain a comparable result. Our results suggest that several canonical assumptions of geometry, regularity and “niceness” in wireless settings can sometimes be relaxed without a significant hit in algorithm performance.

KW - Aggregation

KW - Approximation algorithms

KW - Spanning trees

KW - Wireless capacity

UR - http://www.scopus.com/inward/record.url?scp=85049785138&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85049785138&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ICALP.2018.158

DO - 10.4230/LIPIcs.ICALP.2018.158

M3 - Conference contribution

AN - SCOPUS:85049785138

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018

A2 - Kaklamanis, Christos

A2 - Marx, Daniel

A2 - Chatzigiannakis, Ioannis

A2 - Sannella, Donald

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018

Y2 - 9 July 2018 through 13 July 2018

ER -