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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2008
الحدث2008 IEEE International Symposium on Information Theory, ISIT 2008 - Toronto, ON, كندا
المدة: ٦ يوليو ٢٠٠٨١١ يوليو ٢٠٠٨

سلسلة المنشورات

الاسمIEEE International Symposium on Information Theory - Proceedings
رقم المعيار الدولي للدوريات (المطبوع)2157-8101

!!Conference

!!Conference2008 IEEE International Symposium on Information Theory, ISIT 2008
الدولة/الإقليمكندا
المدينةToronto, ON
المدة٦/٠٧/٠٨١١/٠٧/٠٨

بصمة

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

قم بذكر هذا