A Combinatorial Study of Linear Deterministic Relay Networks - Computer Science > Information TheoryReport as inadecuate

A Combinatorial Study of Linear Deterministic Relay Networks - Computer Science > Information Theory - Download this document for free, or read online. Document in PDF available to download.

Abstract: In the last few years the so-called -linear deterministic- model of relaychannels has gained popularity as a means of studying the flow of informationover wireless communication networks, and this approach generalizes the modelof wireline networks which is standard in network optimization. There is recentwork extending the celebrated max-flow-min-cut theorem to the capacity of aunicast session over a linear deterministic relay network which is modeled by alayered directed graph. This result was first proved by a random coding schemeover large blocks of transmitted signals. We demonstrate the same result with asimple, deterministic, polynomial-time algorithm which takes as input a singletransmitted signal instead of a long block of signals. Our capacity-achievingtransmission scheme for a two-layer network requires the extension of aone-dimensional Rado-Hall transversal theorem on the independent subsets ofrows of a row-partitioned matrix into a two-dimensional variation for blockmatrices. To generalize our approach to larger networks we use thesubmodularity of the capacity of a cut for our model and show that our completetransmission scheme can be obtained by solving a linear program over theintersection of two polymatroids. We prove that our transmission scheme canachieve the max-flow-min-cut capacity by applying a theorem of Edmonds aboutsuch linear programs. We use standard submodular function minimizationtechniques as part of our polynomial-time algorithm to construct ourcapacity-achieving transmission scheme.

Author: S. M. Sadegh Tabatabaei Yazdi, Serap A. Savari

Source: https://arxiv.org/

Related documents