Computer Science – Information Theory
Scientific paper
2009-04-15
Computer Science
Information Theory
24 pages, 2 figures
Scientific paper
In the last few years the so--called "linear deterministic" model of relay channels has gained popularity as a means of studying the flow of information over wireless communication networks, and this approach generalizes the model of wireline networks which is standard in network optimization. There is recent work extending the celebrated max--flow/min--cut theorem to the capacity of a unicast session over a linear deterministic relay network which is modeled by a layered directed graph. This result was first proved by a random coding scheme over large blocks of transmitted signals. We demonstrate the same result with a simple, deterministic, polynomial--time algorithm which takes as input a single transmitted signal instead of a long block of signals. Our capacity-achieving transmission scheme for a two--layer network requires the extension of a one--dimensional Rado--Hall transversal theorem on the independent subsets of rows of a row--partitioned matrix into a two--dimensional variation for block matrices. To generalize our approach to larger networks we use the submodularity of the capacity of a cut for our model and show that our complete transmission scheme can be obtained by solving a linear program over the intersection of two polymatroids. We prove that our transmission scheme can achieve the max-flow/min-cut capacity by applying a theorem of Edmonds about such linear programs. We use standard submodular function minimization techniques as part of our polynomial--time algorithm to construct our capacity-achieving transmission scheme.
Savari Serap A.
Tabatabaei Yazdi M. Sadegh S.
No associations
LandOfFree
A Combinatorial Study of Linear Deterministic Relay Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Combinatorial Study of Linear Deterministic Relay Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Combinatorial Study of Linear Deterministic Relay Networks will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-464308