On the Hardness of Approximating the Network Coding Capacity

DOI10.1109/TIT.2010.2094910zbMath1366.94248OpenAlexW1973643917MaRDI QIDQ5281090

Alex Sprintson, Michael Langberg

Publication date: 27 July 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/tit.2010.2094910

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Coding theorems (Shannon theory) (94A24)

Related Items (6)

Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank ⋮ Local orthogonality dimension ⋮ Unnamed Item ⋮ Linear Index Coding via Semidefinite Programming ⋮ Topological bounds on the dimension of orthogonal representations of graphs ⋮ Unnamed Item

This page was built for publication: On the Hardness of Approximating the Network Coding Capacity