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. We focus on the linear capacity, namely the capacity of the given instance when restricted to linear encoding functions. 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 work we initiate the study of approximation in this context. Namely, we show that given an instance to the general network coding problem of linear capacity C, constructing a linear 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. In addition, we consider the problem of determining the (scalar) linear capacity of a planar network coding instance (i.e., a general instance in which the underlying graph is planar). We show that even for planar networks this problem remains NP-hard.

שפה מקוריתאנגלית
כותר פרסום המארחProceedings - 2008 IEEE International Symposium on Information Theory, ISIT 2008
עמודים315-319
מספר עמודים5
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2008
אירוע2008 IEEE International Symposium on Information Theory, ISIT 2008 - Toronto, ON, קנדה
משך הזמן: 6 יולי 200811 יולי 2008

סדרות פרסומים

שםIEEE International Symposium on Information Theory - Proceedings
ISSN (מודפס)2157-8101

כנס

כנס2008 IEEE International Symposium on Information Theory, ISIT 2008
מדינה/אזורקנדה
עירToronto, ON
תקופה6/07/0811/07/08

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'On the hardness of approximating the network coding capacity'. יחד הם יוצרים טביעת אצבע ייחודית.

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