On the Hardness of Approximating the Network Coding Capacity

DOI10.1109/TIT.2010.2094910MaRDI QIDQ5281090zbMATH OpenOpenAlexFDO

Authors Michael Langberg, Alex Sprintson

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

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

Recommendations

• The encoding complexity of network coding
• Network Coding Capacity With a Constrained Number of Coding Nodes
• On the Capacity of Noncoherent Network Coding
• Network encoding complexity: exact values, bounds, and inequalities
• A computational perspective on network coding
• Deterministic-Coding Capacity of Networks in the Low-Power Regime
• Network Coding: A Computational Perspective
• Network Coding Capacity Regions via Entropy Functions
• An approximation approach to network information theory
• Network Coding for Computing: Cut-Set Bounds

Cited in

(7)

• Linear index coding via semidefinite programming
• Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
• Local orthogonality dimension
• Network coding, does the model need tuning?
• On minrank and the Lovász theta-function
• Topological bounds on the dimension of orthogonal representations of graphs
• Linear index coding via semidefinite programming

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5281090)