On the hardness of approximating the network coding capacity

Michael Langberg, Alex Sprintson

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء


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.

اللغة الأصليةالإنجليزيّة
رقم المقال5695129
الصفحات (من إلى)1008-1014
عدد الصفحات7
دوريةIEEE Transactions on Information Theory
مستوى الصوت57
رقم الإصدار2
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - فبراير 2011

ملاحظة ببليوغرافية

Funding Information:
Manuscript received April 15, 2010; revised August 08, 2010; accepted August 23, 2010. Date of current version January 19, 2011. The work of M. Lang-berg was supported in part by ISF Grant 480/08 and Grant 46114 of the Open University of Israel. The work of A. Sprintson was supported by NSF Grant CNS-0954153. The material in this paper was presented at IEEE ISIT 2008, Toronto, Canada, June 2008.


أدرس بدقة موضوعات البحث “On the hardness of approximating the network coding capacity'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا