TY - GEN

T1 - An information-theoretic meta-theorem on edge-cut bounds

AU - Kamath, Sudeep

AU - Viswanath, Pramod

PY - 2012/10/22

Y1 - 2012/10/22

N2 - We consider the problem of multiple unicast in wireline networks. Edge-cut based bounds which are simple bounds on the rates achievable by routing flow are not in general, fundamental, i.e. they are not outer bounds on the capacity region. It has been observed that when the problem has some kind of symmetry involved, then flows and edge-cut based bounds are 'close', i.e. within a constant or poly-logarithmic factor of each other. In this paper, we make the observation that in these very cases, such edge-cut based bounds are actually 'close' to fundamental yielding an approximate characterization of the capacity region for these problems. We demonstrate this in the case of k-unicast in undirected networks, k-pair unicast in directed networks with symmetric demands i.e. for every source communicating to a destination at a certain rate, the destination communicates an independent message back to the source at the same rate, and sum-rate of k-groupcast in directed networks, i.e. a group of nodes, each of which has an independent message for every other node in the group. We place our work in context of existing results to suggest a meta-theorem: if there is inherent symmetry either in the network connectivity or in the traffic pattern, then edge-cut bounds are near-fundamental and flows approximately achieve capacity.

AB - We consider the problem of multiple unicast in wireline networks. Edge-cut based bounds which are simple bounds on the rates achievable by routing flow are not in general, fundamental, i.e. they are not outer bounds on the capacity region. It has been observed that when the problem has some kind of symmetry involved, then flows and edge-cut based bounds are 'close', i.e. within a constant or poly-logarithmic factor of each other. In this paper, we make the observation that in these very cases, such edge-cut based bounds are actually 'close' to fundamental yielding an approximate characterization of the capacity region for these problems. We demonstrate this in the case of k-unicast in undirected networks, k-pair unicast in directed networks with symmetric demands i.e. for every source communicating to a destination at a certain rate, the destination communicates an independent message back to the source at the same rate, and sum-rate of k-groupcast in directed networks, i.e. a group of nodes, each of which has an independent message for every other node in the group. We place our work in context of existing results to suggest a meta-theorem: if there is inherent symmetry either in the network connectivity or in the traffic pattern, then edge-cut bounds are near-fundamental and flows approximately achieve capacity.

UR - http://www.scopus.com/inward/record.url?scp=84867530186&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84867530186&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2012.6283557

DO - 10.1109/ISIT.2012.6283557

M3 - Conference contribution

AN - SCOPUS:84867530186

SN - 9781467325790

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1657

EP - 1661

BT - 2012 IEEE International Symposium on Information Theory Proceedings, ISIT 2012

T2 - 2012 IEEE International Symposium on Information Theory, ISIT 2012

Y2 - 1 July 2012 through 6 July 2012

ER -