An Approximation Approach to Network Information Theory

This monograph illustrates a novel approach, which is based on changing the focus to seek approximate solutions accompanied by universal guarantees on the gap to optimality, in order to enable progress on several key open problems in network information theory. We seek universal guarantees that are independent of problem parameters, but perhaps dependent on the problem structure. At the heart of this approach is the development of simple, deterministic models that capture the main features of information sources and communication channels, and are utilized to approximate more complex models. The program advocated in this monograph is to use first seek solutions for the simplified deterministic model and use the insights and the solution of the simplified model to connect it to the original problem. The goal of this deterministic-approximation approach is to obtain universal approximate characterizations of the original channel capacity region and source coding rate regions. The translation of the insights from the deterministic framework to the original problem might need non-trivial steps either in the coding scheme or in the outer bounds. The applications of this deterministic approximation approach are demonstrated in four central problems, namely unicast/multicast relay networks, interference channels, multiple descriptions source coding, and joint source-channel coding over networks. For each of these problems, it is illustrated how the proposed approach can be utilized to approximate the solution and draw engineering insights. Throughout the monograph, many extensions and future directions are addressed, and several open problems are presented in each chapter. The monograph is concluded by illustrating other deterministic models that can be utilized to obtain tighter approximation results, and discussing some recent developments on utilization of deterministic models in multi-flow multi-hop wireless networks.