Computer Science – Information Theory
Scientific paper
2011-03-02
Computer Science
Information Theory
Appeared in the 2011 IEEE International Symposium on Information Theory, 5 pages, 1 figure
Scientific paper
We define a notion of network capacity region of networks that generalizes the notion of network capacity defined by Cannons et al. and prove its notable properties such as closedness, boundedness and convexity when the finite field is fixed. We show that the network routing capacity region is a computable rational polytope and provide exact algorithms and approximation heuristics for computing the region. We define the semi-network linear coding capacity region, with respect to a fixed finite field, that inner bounds the corresponding network linear coding capacity region, show that it is a computable rational polytope, and provide exact algorithms and approximation heuristics. We show connections between computing these regions and a polytope reconstruction problem and some combinatorial optimization problems, such as the minimum cost directed Steiner tree problem. We provide an example to illustrate our results. The algorithms are not necessarily polynomial-time.
Kim Anthony
Medard Muriel
No associations
LandOfFree
Computing Bounds on Network Capacity Regions as a Polytope Reconstruction Problem 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 Computing Bounds on Network Capacity Regions as a Polytope Reconstruction Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing Bounds on Network Capacity Regions as a Polytope Reconstruction Problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-473669