Polymatroidal Flows on Two Classes of Information Networks
Dinkar Vasudevan, Satish Babu Korada · IEEE Transactions on Information Theory · 2010
We present inner bounds to the broadcast capacity region of two classes of information networks: Networks of Multiple Access Channels (MACs) and Networks of Deterministic Broadcast Channels (DBCs). Our achievability scheme is a separation based scheme consisting of a physical layer that involves “cleaning up” the constituent channels in the network to create a point-to-point wired overlay, and a network layer that involves routing over this wired overlay. It is shown that finding the optimal way to “clean-up” is equivalent to the problem of finding maximal flows in “polymatroidal” flow networks, an already solved problem. The resulting inner bounds are cut-set bounds evaluated over product input distributions and are tight for Networks of DBCs.