Generalized Cut-Set Bounds for Broadcast Networks Conference Paper

abstract

• 1963-2012 IEEE. An explicit characterization of the capacity region of the general network coding problem is one of the best known open problems in information theory. A simple set of bounds that is often used in the literature to show that certain rate tuples are infeasible are based on the graph-theoretic notion of cut. The standard cut-set bounds, however, are known to be loose in general when there are multiple messages to be communicated in the network. This paper focuses on broadcast networks, for which the standard cut-set bounds are closely related to union as a specific set operation to combine different simple cuts of the network. A new set of explicit network coding bounds, which combine different simple cuts of the network via a variety of set operations (not just the union), are established via their connections to extremal inequalities for submodular functions. The tightness of these bounds are demonstrated via applications to combination networks.

authors

• Liu, Tie

published proceedings

• IEEE TRANSACTIONS ON INFORMATION THEORY

author list (cited authors)

• Salimi, A., Liu, T., & Cui, S.

citation count

• 7

complete list of authors

• Salimi, Amir||Liu, Tie||Cui, Shuguang

publication date

• June 2015

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

• IEEE TRANSACTIONS ON INFORMATION THEORY  Journal

keywords

• Broadcast Networks
• Entropy Inequalities
• Network Coding Bounds
• Submodular Functions

Digital Object Identifier (DOI)

• 10.1109/TIT.2015.2426184

start page

• 2983

end page

• 2996

volume

• 61

issue

• 6

URL

• http%3A%2F%2Fdx.doi.org%2F10.1109%2Ftit.2015.2426184