On the Hardness of Approximating the Network Coding Capacity
On the Hardness of Approximating the Network Coding Capacity
复制标题
DOI：
10.1109/tit.2010.2094910
复制
发表时间：
2008-07
影响因子：
2.5
通讯作者：
M. Langberg;A. Sprintson
中科院分区：
文献类型：
--
作者：
M. Langberg;A. Sprintson
这项工作解决了一般网络编码实例的能力的计算复杂性论文我们在线性和非线性网络编码的上下文中介绍了近似的概念。对于任何一个通用α≤1的通用（即独立于实例的大小）是“硬”。向量线性和非线性编码功能，是解决矢量线性和一般网络编码方案中网络编码能力的计算复杂性的第一个结果。 （标量）平面网络编码实例的线性容量（即，基础图是平面的实例）。
This work addresses the computational complexity of achieving the capacity of a general network coding instance. It has been shown [Lehman and Lehman, SODA 2005] that determining the “scalar linear” capacity of a general network coding instance is NP-hard. In this paper we address the notion of approximation in the context of both linear and nonlinear network coding. Loosely speaking, we show that given an instance of the general network coding problem of capacity C , constructing a code of rate αC for any universal (i.e., independent of the size of the instance) constant α ≤ 1 is “hard”. Specifically, finding such network codes would solve a long standing open problem in the field of graph coloring. Our results refer to scalar linear, vector linear, and nonlinear encoding functions and are the first results that address the computational complexity of achieving the network coding capacity in both the vector linear and general network coding scenarios. In addition, we consider the problem of determining the (scalar) linear capacity of a planar network coding instance (i.e., an instance in which the underlying graph is planar). We show that even for planar networks this problem remains NP-hard.