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
מספר גיליון2
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - פבר׳ 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'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי