Abstract | ||
---|---|---|
Several properties of the inner bound on the region of entropic vectors obtained from representable matroids are derived. In particular, it is shown that: I) It suffices to check size 2 minors of an integer-valued vector to determine if it is a valid matroid rank; II) the subset of the extreme rays of the Shannon outer bound (the extremal polymatroids) that are matroidal are also the extreme rays of the cone of matroids; III) All matroid ranks are convex independent; and IV) the extreme rays of the conic hull of the binary/ternary/quaternary representable matroid ranks inner bound are a subset of the extreme rays of the conic hull of matroid ranks. These properties are shown to allow for substantial reduction in the complexity of calculating important rate regions in multiterminal information theory, including multiple source multicast network coding capacity regions. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1109/Allerton.2013.6736606 | Allerton |
Keywords | Field | DocType |
matroids,shannon outer bound,quaternary representable matroid rank,extremal polymatroids,entropic vectors,binary representable matroid rank,multiterminal information theory,matrix algebra,multiple source multicast network coding capacity regions,entropic vector region,polymatroids,combinatorial mathematics,computational complexity,integer-valued vector,matroid bounds,ternary representable matroid rank,entropy,substantial reduction,vectors,network coding | Matroid,Information theory,Discrete mathematics,Mathematical optimization,Combinatorics,Oriented matroid,Regular polygon,Matroid partitioning,Graphic matroid,Conic section,Weighted matroid,Mathematics | Conference |
ISSN | ISBN | Citations |
2474-0195 | 978-1-4799-3409-6 | 2 |
PageRank | References | Authors |
0.42 | 9 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Congduan Li | 1 | 40 | 7.75 |
John MacLaren Walsh | 2 | 107 | 17.90 |
Steven Weber | 3 | 724 | 53.55 |