|| Exponentially Simpler Network Rate Regions
||Yirui Liu, John MacLaren Walsh, Drexel University, United States; , |
||D6-S2-T1: Network Coding Tradeoffs
||Monday, 19 July, 22:20 - 22:40
||Monday, 19 July, 22:40 - 23:00
Determining the rate region of a network is of great importance in the research area of network coding. Lots of attempts have been made and significant progress has been achieved over the last decade on this topic. Although these researches provide us with multiple ways of calculating the outer or inner bounds of rate region, the sheer complexity of the problem, which involves expressing and projecting a very high dimensional polyhedra, makes it computationally infeasible beyond networks with 10s of edges. Aimed at reducing the complexity of the rate region calculation, in this paper a new theorem that implicitly determines the rate region of a network is proved and a corresponding systematic way of applying the theorem to calculate explicitly the outer bounds to a rate region is proposed. Compared with the traditional method, the proposed method has the potential to calculate the true rate region via the projection of simpler polyhedra that has exponentially less dimensions and is characterized by exponentially less facets.