Generalized cut-set bounds for broadcast networks
Generalized cut-set bounds for broadcast networks
复制标题
广播网络的广义割集界限
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Shuguang Cui
中科院分区：
文献类型：
--
作者：
Amir Salimi;Tie Liu;Shuguang Cui
一般网络编码问题的容量区域的明确表征是信息论中最著名的开放问题之一。在文献中经常使用一组简单的界限来表明某些速率元组是不可行的，这是基于图论的切的概念。然而，当网络中有多个消息要通信时，标准的割集边界通常是宽松的。本文以广播网络为研究对象，广播网络的标准切集边界与并集密切相关，是将网络的不同简单切集组合在一起的一种特定集合操作。通过与子模函数的极值不等式的联系，建立了一组新的显式网络编码界，它通过各种集合操作（不仅仅是联合）组合了网络的不同简单切割。通过组合网络的应用证明了这些边界的严密性。
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 are 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.