Generalized Network Sharing Outer Bound and the Two-Unicast Problem
Sudeep Kamath, David N. C. Tse, Venkat Anantharam · 2011
Abstract — We describe a simple improvement over the Network Sharing Bound [1] for the multiple unicast problem. We call this the Generalized Network Sharing (GNS) Outer Bound. We note two properties of this bound with regard to the two-unicast problem: a) it is the tightest bound that can be realized using only edge-cut bounds and b) it is tight in the special case when all edges except those from a so-called minimal GNS set have sufficiently large capacities. Finally, we present an example showing that the GNS outer bound is not tight for the two-unicast problem.