论文标题
在未指向Unicast网络信息能力的分区中
On the Partition Bound for Undirected Unicast Network Information Capacity
论文作者
论文摘要
信息理论中重要的未解决的问题之一是，猜想是网络编码与无向单播网络中的路由相比没有速率益处。在未指向的单播信息网络中，对称速率的三个已知界限是最稀少的切割，LP结合和分区结合。在本文中，我们在分区界面介绍了三个结果。我们表明，计算分区界限的决策版本问题是NP完整的。我们为两类网络提供了最佳路由方案的完整证明，这些网络获得了分区的界限。最近，对新的网络类证明了猜想，并证明了以前证明的所有网络实例是该类别的元素。我们显示了一个网络的存在，该网络的分区绑定是紧密的，可以通过路由实现，并且不是这类新网络的元素。
One of the important unsolved problems in information theory is the conjecture that network coding has no rate benefit over routing in undirected unicast networks. Three known bounds on the symmetric rate in undirected unicast information networks are the sparsest cut, the LP bound and the partition bound. In this paper, we present three results on the partition bound. We show that the decision version problem of computing the partition bound is NP-complete. We give complete proofs of optimal routing schemes for two classes of networks that attain the partition bound. Recently, the conjecture was proved for a new class of networks and it was shown that all the network instances for which the conjecture is proved previously are elements of this class. We show the existence of a network for which the partition bound is tight, achievable by routing and is not an element of this new class of networks.
